First,we can consider that each $$$c_i$$$ is independant.So,we can calc the answer of each $$$c_i$$$.Then we calc their sums.

Then,obviously,we can discover $$$i$$$ is important for us to use it if there is $$$j$$$,$$$a_j\le a_i$$$ and $$$a_j-b_j\le a_i-b_i$$$。Because we can use $$$j$$$ to replace $$$i$$$ and we can save more objects.

Therefore,we can let $$$d_i=a_i-b_i$$$ and sort $$$(a_i,d_i)$$$ in the order of $$$a_i$$$.Then a useful $$$(a_i,d_i)$$$ means there isn't $$$j \lt i$$$,$$$d_j\le d_i$$$.So we can record $$$k=\min_{1\le j \lt i} d_j$$$，$$$d_i \lt k$$$。

Like this:

[submission:267715465]

Then,we use dp algorithm to solve it. Let $$$f_i$$$

Obviously,$$$f_i=f_{i-d_j}+1$$$,$$$j$$$ is the maxnum $$$x$$$,$$$a_x\le i$$$.

Because $$$a_i\le 10^6$$$,we only calc for $$$i\le 10^6$$$.

For $$$i \gt \max a$$$,we can reduce it to $$$i-kd$$$ by use $$$max a$$$.$$$k=\lfloor\frac{i-\max a}{d}\rfloor+1$$$

you can use unordered_map

since a[i]-b[i] <= 10^6, use an array instead is sufficient

1 dbcebd eddedad answer:10 since the first letter of b may not in a.

I also think so. And I'm Chinese, I can't watch the videos on youtube.

consider this a-> abc b->xaxbxcx here lcs is 3(abc) so according to you ans must be 3+7-3 but actual ans is 9 ie 3+7-1

Well no its not . Suppose you get first strings abcde and the other as bfd , the actual answer of this will be 7 , it is basically the longest sequence of string a which is also subarray of string b.

This solution also:- 267735052

UPD: This solution is actually correct.

The authors are gonna upload the text tutorials. Not uploading the text tutorials in favor of video editorials would be a retarded decision. Video tutorials are just like a bonus for whoever learns better by watching.

I Used the exact same idea. He got wrong answer and not TLE. Maybe he missed some boundary condition. This is my submission using same idea, if it helps 267852076

I have corrected his code. This is his code with modifications https://codeforces.me/contest/1989/submission/267873425

[deleted]

These video tutorials are unofficial, text editorials will be released soon by the contest authors.

Your idea is incorrect because whenever you get that b[i] == a[j] you are assuming that taking that a[j] will give you the best answer that isn't necessarily true. For example, there is this test case:

1 bba abb

In C++, comparator should return false if its arguments are equal.