Then there is google hashcode on 24. Man, this week is packed with excitement for programmers.

count the cells which must be missed.

After processing the first $$$i$$$ characters, lets suppose we are at some position $$${x, y}$$$ .

Assume wlog we have $$$s_{i} = D$$$.

We clearly can't even reach points with $$$x' \lt x$$$ or $$$y' \lt y$$$, so let's assume we've marked them as unreachable in the previous $$$i - 1$$$ steps.

If this is the last character, we can clearly reach all points with $$$x' \geq x$$$ and $$$y' \geq y$$$, so we don't need to subtract anything. Otherwise we don't need to worry about points with $$$x' \gt x$$$, since the next position (which will be on row $$$x + 1$$$ since $$$s_{i} = D$$$) is better suited to that task since any repetition from that point will use the same sequence of repetitions, except for one less downward step.

So that leaves the points to the right on the same row. If the character $$$R$$$, appears $$$k$$$ more times after position $$$i$$$ of the string, then we will go out of the grid trying to access the last $$$k$$$ columns of this row, so they are unreachable. The rest can clearly be reached by repeating the last occurrence of $$$R$$$ before position $$$i$$$.

So we just need to subtract $$$k$$$ from the answer at this position. Any further position is in a lower row so we won't overcount.

We can see due to symmetry the same holds for $$$s_i = R$$$ with $$$D$$$ occuring $$$k$$$ more times after position $$$i$$$.

One last thing to be careful about, is that for the first substring of equal characters, there is no character to move us downward / right to reach those cells perpendicular to our direction of motion, so we always have to subtract $$$n - 1$$$ in that case.

Solution — 147333480

Did one of them actually passed the system tests ?

I just reversed the first half and second half for every partition at index (1,n)

Once you know the solution, you will facepalm. I figured it out after spending more then an hour and ha half and it's soo simple I was overcomplicated it. Wasted D tho :(

Once you figure out its DP, it becomes easy.

DP[i][j] — max continous subarray sum upto the ith index in array and j addition of X.

Look carefully at the constraints on $$$n$$$ and $$$m$$$

n & m can be large per testcase you can use set instead.

First, we will calculate the max sum for each subarray for length i=0,n, We can do this just by 2 simple FOR loops. So now we have an array SubArraySum[], and subArraySum[i] represents the max sum among the ith length subArray. Now to find the best answer when we can add some k elements of value x, we can do this by iterating over the subArraySum array, and for a SubArray of length =i we can increase its value by x*min(k,i).

I've observed the same thing recently, with EDUs being ridiculously free :thinking:

I agree, although I feel like this contest in particular was pretty easy even for an EDU.

you are creating vectors inside the test case loop, n,m can be upto 2e5. doing this vector creation of this much size t(testcases) time, leads to TLE. To solve this you need to create the vectors outside the test case loop and set and unset it

It does not guarantee that the sum of M and N is within the 1e5 range.

The problem is declaring again and again those 3 vectors, because of n and m being up to 2e5 every time, it takes a lot of time to always fill the vectors. A simple replacement of those with a map and declaring one of them global will do the trick (Of course, with .clear() before each testcase). Here is your solution but modified as said above : https://codeforces.me/contest/1644/submission/147351646

Process queries in reverse order. Then for any query q, check if either you have seen the row and the column of this query before (in which case this query shouldn't be counted), or if all the rows or all the columns have been painted already (again, in which case this query shouldn't be counted).

Now we know all queries that should be counted (call them valid_queries), the answer is simply $$$k^{validqueries}$$$.

https://codeforces.me/contest/1644/submission/147343490

wait, what problem were you thinking about exactly lol? cus the answer changes depending on the coordinates xD

At the beginning I thought that I can change the order of q operations

Rating changes are not immediate

The first permutation is n,n-1,...,1. Let's say this is (1).

Then just swap every adjacent pair of (1). There are n-1 adjacent pairs so you will get total n pairs.

Let's understand this with an example of n=4.

1: 4 3 2 1

2: 3 4 2 1

3: 4 2 3 1

4: 4 3 1 2

you may think about how to construct an answer for $$$n$$$ when an answer for $$$n-1$$$ is known.

Sort the permutation in descending order and shift the smallest element (i.e 1) one place at a time from right to left. For example if n=4:

4->3->2->1, 4->3->1->2, 4->1->3->2, 1->4->3->2

Failing testcase: Ticket 485

me getting hacked after passing test case 6 in 1996 ms ,used normal map xD

I used a segment tree.

i think i did without dp, though after the contest

You can just find the max sum for each subsegment for a fixed size for all sizes from 1 to n. and then just try all values of max with given k

my implementation.

#define int long long

void solve() {
    int n, x; cin >> n >> x;
    vector<int> a(n), pre(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    pre[0] = a[0];
    for (int i = 0; i < n - 1; i++)
        pre[i + 1] = pre[i] + a[i + 1];
    vector<int> ma(n + 1, -1e18);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sub = pre[j] - (i ? pre[i - 1] : 0);
            int siz = j - i + 1;
            ma[siz] = max(ma[siz], sub);
        }
    }
    for (int k = 0; k <= n; k++) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, ma[i] + x * min(i, k));
        }
        cout << ans << ' ';
    }
    cout << '\n';
}

Me, well don't exactly know if it would be called as DP or not, but there was a little bit of pre-calculation for calculating the maximum possible sums of each of subarrays and then finally iterating over them to get optimal answer for each k from 0 to n.

vector mxsum(n+1,INT_MIN);

mxsum[0]=0;
for(int i=0;i<n;i++)
{
    int sum=0;
    for(int j=i;j<n;j++)
    {
        sum+=a[j];
        mxsum[j-i+1]=max(mxsum[j-i+1],sum);
    }
}

I was not able to solve it in time either(cause stupid me thought it was impossible to calculate the sum of Stirling numbers fast enough). But since I hate NTT and I like this problem I have upsolved it without NTT in O(n * sqrt(n))147355537
After some optimizations(147356152) it is now running in 1,5 seconds, wich is 1/4 of TL, so maybe this solution is actually intendent

123 people did random shuffle in B

which n gives the highest chances for hacking? :D

Your solution is exactly $$$O(nT)$$$, and there isn't any constrant on $$$\sum n$$$.

The hacker generated a testdata with $$$t = 10000, n = m = k = 2\times 10^5, q = 20$$$ to maximize $$$\sum n$$$.