Guessing problem from contest number is very useful for ABC.

obviously primes which are palindromes

認同

Changing solve() to the following makes it accepted:

void solve(){
    for(int i=1; i<=n; i++){
        __int128 nleft=get(1, 1, m, 1, t[i]).fi;
        __int128 nright=get(1, 1, m, t[i], m).se;
        dp[i]=p[i]+max((__int128)-t[i]*c+nleft, (__int128)t[i]*c+nright);
        update(1, 1, m, t[i], {dp[i]+t[i]*c, dp[i]-t[i]*c});
    }
    cout << max((ll)0, (ll)*max_element(dp, dp+n+1));
}

The changes are that the for loop bound is n instead of m, and at the end take the maximum between 0 and the dp maximums to handle the case if it is better to not participate in any market at all.

There is a corner case for K=2

Example

2
2 0
6 0

Answer is 3

your solution might be O(n * n) just sort the array and use binary search

Hi, amazing solution and explanation. I have one doubt though. While choosing the optimal position to the right of current index (say t), why are you checking for the max value in range [t,n-1] ? Shouldn't it be [t+1,n-1] ?

Define $$$dp[i]$$$ to be the profit when you end your journey at index $$$i$$$.

Then, define $$$ldp[i] = dp[i] + c \cdot i$$$ and $$$rdp[i] = dp[i] - c \cdot i$$$.

Then, $$$dp[t]$$$ would take contribution from prefix maxima of $$$ldp$$$ and suffix maxima of $$$rdp$$$. So a Segment Tree or Fenwick Tree suffices.

Tbh G was simpler than C to me. It could have easily been an E, considering it was quite literally just about implementing a segtree.

Isnt segment tree somewhat basic? Specially without lazy propagation, it is a very common topic, a little bit more advanced than binary search. You can just learn to use it as a black box, it is easier to learn than dynammic programming, about the same level as dijkistra or fast pow IMO.

Got AC using double hash

comment

If you convert to int as in (int)1e8 it should work. It's the double comparison that is giving you troubles most likely.

Corner case for K=2 probably?

2
2 0
6 0

Answer is 3

Hi,this Code for F gives WA in 6 testcases,can you help?

same

it's O(n^2) and n <= 1e5. btw you could also write this soln with 2 for loops why did you complicate it

Maybe your mistake is when there are 2 markets in the same location one after the other, are you handling this correctly?

When calculating $$$c*(y+1)$$$ you may have an overflow.

You are mixing up the zero based indexing and one based indexing. Here's your almost correct solution, where I used zero based indexing for segtree as well as $$$|.|$$$ operator. After the fix, your code passed 55 testcases instead of just 14 testcase.

The rest 18 testcases fail due to a completely different issue, which is obvious to me, but I'll let you figure out and debug on your own. If you are still not able to, feel free to ping on the thread.

Use long long instead of int. I changed your code and submitted. Now it is AC.