Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main(args: Array<String>) {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()
println(minOf(a[1] - 1, n - 2))
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> a(n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
int pos = max_element(a.begin(), a.end()) - a.begin();
bool res = true;
for(int i = 0; i < pos; i++)
res &= (a[i] < a[i + 1]);
for(int i = pos; i < n - 1; i++)
res &= (a[i] > a[i + 1]);
if(res)
puts("YES");
else
puts("NO");
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int n, k;
int a[N];
int main(){
cin >> n >> k;
for(int i = 0; i < n; ++i)
cin >> a[i];
vector <int> v;
for(int i = 1; i < n; ++i) v.push_back(a[i - 1] - a[i]);
sort(v.begin(), v.end());
int res = a[n - 1] - a[0];
for(int i = 0; i < k - 1; ++i) res += v[i];
cout << res << endl;
return 0;
}
```

1197D - Yet Another Subarray Problem

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int n, m, k;
int a[N];
long long bst[N];
long long psum[N];
long long sum(int l, int r){
l = max(l, 0);
return psum[r] - (l == 0? 0 : psum[l - 1]);
}
int main() {
cin >> n >> m >> k;
for(int i = 0; i < n; ++i){
cin >> a[i];
psum[i] = a[i] + (i == 0? 0 : psum[i - 1]);
}
long long res = 0;
for(int len = 1; len <= m && len <= n; ++len)
res = max(res, sum(0, len - 1) - k);
for(int i = 0; i < n; ++i){
if(i + 1 >= m){
long long nbst = sum(i - m + 1, i) - k;
if(i - m >= 0) nbst += bst[i - m];
bst[i] = max(bst[i], + nbst);
}
for(int len = 0; len < m && i + len < n; ++len)
res = max(res, bst[i] + sum(i + 1, i + len) - k * (len > 0));
}
cout << res << endl;
return 0;
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
const int INF = int(1e9) + 555;
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const int MOD = int(1e9) + 7;
int norm(int a) {
if(a >= MOD) a -= MOD;
if(a < 0) a += MOD;
return a;
}
pt combine(const pt &a, const pt &b) {
if(a.x < b.x)
return a;
if(a.x > b.x)
return b;
return {a.x, norm(a.y + b.y)};
}
int n;
vector<pt> p;
inline bool read() {
if(!(cin >> n))
return false;
p.resize(n);
fore(i, 0, n)
cin >> p[i].x >> p[i].y;
return true;
}
vector<pt> T;
void setVal(int pos, const pt &val) {
T[pos += n] = val;
for(pos >>= 1; pos > 0; pos >>= 1)
T[pos] = combine(T[2 * pos], T[2 * pos + 1]);
}
pt getMin(int l, int r) {
pt ans = {INF, 0};
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1)
ans = combine(T[l++], ans);
if(r & 1)
ans = combine(T[--r], ans);
}
return ans;
}
inline void solve() {
auto comp = [](const pt &a, const pt &b) {
if(a.y != b.y)
return a.y < b.y;
return a.x < b.x;
};
sort(p.begin(), p.end(), comp);
T.assign(2 * n, {INF, 0});
for (int i = n - 1; i >= 0; i--) {
int pos = int(lower_bound(p.begin(), p.end(), pt(0, p[i].x), comp) - p.begin());
if(pos >= n) {
setVal(i, {p[i].y, 1});
continue;
}
pt bst = getMin(pos, n);
setVal(i, {bst.x - (p[i].x - p[i].y), bst.y});
}
cout << getMin(0, n).y << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
return (x + y) % MOD;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
typedef vector<int> vec;
typedef vector<vec> mat;
vec mul(const mat& a, const vec& b)
{
int n = a.size();
int m = b.size();
vector<int> c(m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
c[i] = add(c[i], mul(b[j], a[i][j]));
return c;
}
mat add(const mat& a, const mat& b)
{
int n = a.size();
int m = a[0].size();
mat c(n, vec(m, 0));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
c[i][j] = add(a[i][j], b[i][j]);
return c;
}
mat mul(const mat& a, const mat& b)
{
int x = a.size();
int y = b.size();
int z = b[0].size();
mat c(x, vec(z, 0));
for(int i = 0; i < x; i++)
for(int j = 0; j < y; j++)
for(int k = 0; k < z; k++)
c[i][k] = add(c[i][k], mul(a[i][j], b[j][k]));
return c;
}
mat binpow(mat a, int d)
{
int n = a.size();
mat c = mat(n, vec(n, 0));
for(int i = 0; i < n; i++) c[i][i] = 1;
while(d > 0)
{
if(d % 2 == 1) c = mul(c, a);
a = mul(a, a);
d /= 2;
}
return c;
}
int f[3][3];
int extend(int color, vector<int> last_numbers)
{
vector<int> used(4, 0);
for(int i = 0; i < 3; i++)
if(f[color][i])
used[last_numbers[i]] = 1;
for(int i = 0; i <= 3; i++)
if(used[i] == 0)
return i;
return 3;
}
vector<int> extend_state(int color, vector<int> last_numbers)
{
int z = extend(color, last_numbers);
last_numbers.insert(last_numbers.begin(), z);
last_numbers.pop_back();
return last_numbers;
}
vector<int> int2state(int x)
{
vector<int> res;
for(int i = 0; i < 3; i++)
{
res.push_back(x % 4);
x /= 4;
}
return res;
}
int state2int(const vector<int>& x)
{
int res = 0;
int deg = 1;
for(auto y : x)
{
res += deg * y;
deg *= 4;
}
return res;
}
mat form_matrix(int color)
{
mat res(64, vec(64, 0));
for(int i = 0; i < 64; i++)
{
int j = state2int(extend_state(color, int2state(i)));
res[j][i] = add(res[j][i], 1);
}
return res;
}
mat color_matrices[3];
mat full_matrix;
vector<pair<int, int> > colored[1043];
int len[1043];
int dp[1043][4];
mat full_pows[31];
void precalc_pows()
{
full_pows[0] = full_matrix;
for(int i = 0; i <= 30; i++)
full_pows[i + 1] = mul(full_pows[i], full_pows[i]);
}
vec powmul(int d, vec b)
{
for(int i = 0; i <= 30; i++)
{
if(d % 2 == 1)
b = mul(full_pows[i], b);
d /= 2;
}
return b;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> len[i];
int m;
cin >> m;
for(int i = 0; i < m; i++)
{
int x, y, c;
cin >> x >> y >> c;
--x;
--y;
--c;
colored[x].push_back(make_pair(y, c));
}
for(int i = 0; i < n; i++)
sort(colored[i].begin(), colored[i].end());
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
cin >> f[i][j];
for(int i = 0; i < 3; i++)
color_matrices[i] = form_matrix(i);
full_matrix = color_matrices[0];
for(int i = 1; i < 3; i++)
full_matrix = add(full_matrix, color_matrices[i]);
precalc_pows();
dp[0][0] = 1;
for(int i = 0; i < n; i++)
{
vec cur(64);
cur[state2int({3, 3, 3})] = 1;
int last = 0;
for(auto x : colored[i])
{
cur = powmul(x.first - last, cur);
cur = mul(color_matrices[x.second], cur);
last = x.first + 1;
}
cur = powmul(len[i] - last, cur);
for(int j = 0; j < 4; j++)
for(int k = 0; k < 64; k++)
{
vector<int> s = int2state(k);
dp[i + 1][j ^ s[0]] = add(dp[i + 1][j ^ s[0]], mul(dp[i][j], cur[k]));
}
}
cout << dp[n][0] << endl;
}
```

I challenge you to write D in $$$O(n)$$$

SolutionFirst of all if $$$m \geq n$$$, let's make $$$m = n$$$.

Let's us look at some segment $$$[l, r]$$$. The actual cost of it is $$$\sum_{l}^{r} a_i - \left \lfloor{\frac{r - l + 1}{m}}\right \rfloor \cdot k - (k$$$ or $$$0)$$$ depending on the segment. Let's subtract $$$k$$$ from each $$$a_{m \cdot i}$$$. Now we can be sure that the cost of $$$[l, r]$$$ is $$$\sum_{l}^{r} a_i - (k$$$ or $$$0)$$$ depending on the segment. How to differ those cases? Let's look at a half-interval $$$(l - 1, r]$$$. $$$\sum_{l}^{r} a_i$$$ is equal to $$$prefsum_r - prefsum_{l - 1}$$$. How do we define whether we should subtract $$$k$$$ or not? Let's look at $$$r \pmod m$$$ and $$$l - 1 \pmod m$$$. If $$$l - 1 \pmod m \geq r \pmod m$$$ than we alredy subtracted the right amount of $$$k$$$'s. Otherwise we should subtract another $$$k$$$.

Let's write it in $$$O(n \cdot m)$$$. Let's maintain $$$m$$$ values $$$mn_i =$$$ minimal prefsum of some index $$$j$$$ such that $$$i \equiv j \pmod m$$$. Now let's run from $$$0$$$ to $$$n - 1$$$ with index $$$i$$$. On each iteration let's consider all segments such that right bound is $$$i$$$. Now run through $$$mn$$$ and and update our answer if we could. After that let's make $$$mn_{i \pmod{m}} = min(mn_{i \pmod{m}}, prefsum_i)$$$.

Now how to make it $$$O(n)$$$. let's notice that answer for $$$i$$$'th index is $$$prefsum_i$$$ — $$$min(min(mn[0..i$$$ $$$\%$$$ $$$m - 1]) + k,$$$ $$$ min(mn[i$$$ $$$\%$$$ $$$m..m - 1]))$$$. So basically we need suffix minimum, prefix minimum and update one value (the first value in current suffix). Let's process each block of length m separately. For each block let's update suffix minimum in $$$m - 1$$$ updates. Let's define prefix minimum as $$$p = \infty$$$. Now while running through $$$i$$$ to $$$i + m$$$ let's update $$$mn_{i \pmod{m}}$$$ with $$$prefsum_i$$$ and after updating answer with $$$prefsum_i - min(p + k, suffmn_{i \% m})$$$ update $$$p$$$ as $$$min(p, mn_{i \% m})$$$. On each block it takes $$$O(m)$$$ iterations, and there are at most $$$\left \lceil{\frac{n}{m}}\right \rceil$$$ blocks. So it's $$$\left \lceil{\frac{n}{m}}\right \rceil \cdot O(m) = O(n)$$$, as $$$m \leq n$$$.

You can also notice that this solution doesn't need to store all the array, so the only memory it takes is $$$m$$$ values of $$$mn$$$ and other $$$O(1)$$$ values. So it's $$$O(n)$$$ in time and $$$O(min(n, m))$$$ in memory. This solution is the fastest of all and also uses 0KB of memory.

UPD: you can also optimize the solution I've written below using queue minimum. But it's not as nice and causes bigger constant.What's the intuition behind D?

I can explain a different (easier) solution. Let's define $$$dp_i$$$ as answer, such that $$$i$$$ is the last used element. Now $$$dp_i = max(0, a_i - k, max(dp[j] - k + \sum_{j + 1}^{i} a_t)$$$, where $$$i - j \leq m$$$. The intuition is as follows: we need to divide all the segment, into subsegments, each length $$$\leq m$$$.

I used the technique but the it fails on test case 19 here is the link to it.

It's a little hard to understand your code. This is the implementation of what I wrote.

Hm that's kinda weird, cause when I tried to implement it here (https://codeforces.com/contest/1197/submission/57633664) I ran into problems with it applying the "k" penalty more times than it should

In the end I implemented a solution that uses a second "tolerance" value ( = (-len) mod m ) to indicate how many more values the subarray could take before the k penalty should be applied again: https://codeforces.com/contest/1197/submission/57643293 but now I'm puzzled as to why your code works without it! :P

EDIT: Oh, I just realized that the first code sample had an issue where I wasn't getting the correct results for subarrays [0..i], where 1 < i < m . This bit me later in the butt in another test. The code now works without needing a tolerance term: https://codeforces.com/contest/1197/submission/57646083

Can you explain a bit more the meaning of each term in the recursive formula in terms of the decision it represents?

Basically we want to find the best segment, such that after splitting it into $$$cnt$$$ subsegments each length $$$\leq m$$$, $$$\sum_{l}^{r} a_i - cnt \cdot k$$$ is maximum. So when we want to count $$$dp_i$$$, we take all lengths $$$1$$$ to $$$m$$$ and try to make $$$[i - len + 1, i]$$$ the last of subsegments. That's how we update dp. This solution relies on the fact that $$$k \geq 0$$$.

so for this solution, how does it take into account segments with length > m?

Every segment consists of subsegments of length $$$\leq m$$$. For each small subsegment you have to subtract $$$k$$$. So each segment is just continuous merge of small subsegments. That's why we can apply DP. Each segment is either a small segment or a merge of segment and a small segment.

This easier solution is O(m*n) right?

Yes

You can check my solution, Only $$$j = i - m$$$ needs to be considered, Otherwise just take max subarray ending at $$$i$$$ with length $$$\leq m$$$.

Yes, your solution is actually the same, I simply don't differ those cases. It still works in $$$O(n\cdot m)$$$.

It can actually be improved to $$$O(n)$$$ easily by also storing the 2 best subarrays of length $$$\leq m$$$ for $$$i - 1$$$ so you don't have to do a for loop.

consider this case: say $$$j = i - 1, dp_j = a_j - k$$$, when you try to update the value for $$$dp_i$$$ using $$$dp_j - k + a_i$$$, $$$k$$$ will be deducted twice when you calculate $$$dp_i$$$. Is that the case or am I misunderstanding something?

Yes, in this case it subtracts twice, but we will find the best answer anyway.

Is it ok for you to explain why this is the case?

I assume that

[i, i]is the last small segment. It means that beforeithere were small segments only of lengthm. This leads to another subtraction as[i, i]is a different segment.I mean why we can still find the optimal answer despite that k is subtracted twice

This is the situation, where length is

x * m + 1, we have to subtractkx + 1times.I kindda get your idea after re-reading your comments. In your method, although $$$dp[i]$$$ is miscalculated when we try to update it using $$$dp[i-1]$$$, the optimal answer will surface out when we try to update it using $$$dp[i-2]$$$, is that the case?

Yes, we choose the maximal value of all, so we will get the best answer.

I think I finally get it. Thanks for answering my questions patiently!

I don't understand the solution for C, I guess this solution works because the initial array is sorted? Is there known algorithm that leads to this solution using differences between adjacent elements?

https://codeforces.com/blog/entry/68553?#comment-529278 may be this comment will help u !!

Let

a[1], a[2].. a[n]be the elements in the array. Let 1 <= i < j < k < l....< n be the k-1 indices we choose for dividing the array into k segments. So, cost of division =(a[i] — a[1]) + (a[j] — a[i+1]) + .... + (a[k] — a[j+1]) + (a[n] — a[k+1]), on rearranging :(a[n] — a[1]) — ((a[i+1] — a[i]) + (a[j+1] — a[j]) +.....+ (a[k+1] — a[k])). So, we will store the difference of a[i+1]-a[i] for each 1<=i<n , sort them in decreasing order and take first k-1 differences and finally subtract from (a[n]-a[1]).To start with, we have to break array on k segments. Let's create an array of differences: let d[i] = a[i+1]-a[i]. For a better understanding of the phrase "break array on k segments" let's say that we have to put k-1 partitions between numbers in array. Then, let's look on the answer, when we put each partition in the array: at the beginning the answer is equal to a[n-1]-a[0] = (a[1]-a[0])+(a[2]-a[1])+...+(a[n-1]-a[n-2]) = d[0]+...+d[n-2], after breaking the array into two parts (let's say that we put the partition between a[q+1] and a[q], 0 <= q < n-1) then the answer will be equal to (a[n-1]-a[q])+(a[q-1]-a[0]) = (a[1]-a[0])+...+(a[q-1]-a[q-2])+(a[q+1]-a[q])+...+(a[n-1]-a[n-2]) = d[0]+...+d[q-2]+d[q]+...+d[n-2]. Then, it is easy to notice that with each new partition we can delete 1 element from array d to decrease the answer, so let's delete k-1 biggest elements from d and sum up the rest, this will be the answer to the problem :) PS. Sorry for my bad English :p

nice explaintaion!!!

Can someone explain how to solve E problem. Why do we need a segment tree. And how do we find the value of the minimum for the whole set of the dolls?

If there is no $$$j$$$, that $$$matryoshka_j.in \ge matryoshka_i.out$$$, then $$$d_i = (matryoshka_i.in, 1)$$$

else

$$$d_i.first = min[pos,n] - (matryoshka_i.out - matryoshka_i.in)$$$, where $$$pos$$$ is the first $$$j$$$, that $$$matryoshka_j.in \ge matryoshka_i.out$$$ (It means that we can put matryoshka $$$i$$$ inside matryoshka $$$j$$$)

$$$d_i.second = numberOfMinimums[pos,n]$$$

And $$$d$$$ — is our segment tree, so we need it to calculate minimum and number of minimums on suffix!

You can check my solution, I think it's clear enought.

yep , your solution is self descriptive , but i have seen this https://codeforces.com/contest/1197/submission/57527419 which doesn't even use segtree , like no heavy DS stuff .

I haven't mastered segment trees yet (did an object-pointer based one for practice but probably need to learn how to do it with bitwise-math and array indices for better efficiency) but I managed to solve this one using only a priority queue; code here if interested:

https://codeforces.com/contest/1197/submission/57589994

What does

`len`

mean in the editorial of D? And how does that expression`len * m`

come?I suppose len is the number of segments that are fully covered. So $$$best_i$$$ is the answer if only segments of length divisible by m are considered.

len means the mutiple of m u r checking backwards from your current position as u need to check only multiples of m for the correct answer from any given position

Thanks a lot! I think I got it.

I come with something for problem D but I can't develop it to a solution if anyone solves it by the help of the following please tell me:

we deal with the array as the blocks, we try each possible one let's call it j from 1 to m, and for every j we try to start from 0 to j — 1 and move by j step to partition the array.

it does nothing but I think it could be developed in some way.

Very nice explanation of problem E. Thank you so much)

why is it besti+sum(i−len,i−1)−k. in the end and not besti + sum(i-len+1,i) — k ?

Sorry i got it now it's correct.

I was discussing problem E with my friend SparklingRa1n and after he solved it we read the editorial. And we noticed this part (

It's because not big enough subsets are not optimal in terms of minimality of extra space.)However, we are not sure if the part that adedalic says is true, please correct us if we're wrong.

Take this example with 2 dolls

`{4, 1} {6, 5}`

The minimum extra space of big enough is 2, but if you take the first doll only, the extra space is 1

Let's extend your example as

`{2,1} {4,2} {6,5}`

$$$d[3] = (5, 1)$$$ — it should be obvious. When we try to calculate $$$d[2]$$$ we can see, that the second matryoshka can be nested inside the third one — so "we must put it inside". Then $$$d[2] = (5-2=3, 1)$$$.

The first doll can be nested both in the second and third dolls, but putting it inside the third doll will lead us to not

big enoughsubset. But! it also makes the extra spacenot optimalsince $$$d[2].first < d[3].first$$$. Then $$$d[1] = (3-1=2, 1)$$$ and it's correct.Ohh, I understand, I was a little confused, but now is totally clear. Thanks.

Can someone explain the intution behind D and as to how are we connecting the maximum sum subarray problem to this problem in greater depth. Also I'm not able to understand the intuition behind the idea of introducing len (as done in the editorial) Please help.

This is an alternate Solution 57537548 of Problem 1197C - Array Splitting

In problem E, Why cann't we add subset {4,7} as one of good subsets in Test Case 1.

Because it is not big enough. We can put $$$7$$$ inside other doll

ok,got it.

can someone give me some further explanations about problem c? more specific: why should we "add up the k−1 minimal ones to the answer"?

In the solution given for D why do we fix some elements of best_i with best_i + sum(i-len,i-1) — k ?

I think this is a typo: https://codeforces.com/blog/entry/68615?#comment-530337

Can someone explain in more details solution of C, with proofs? Thanks

you will only break, if consecurtive numbers have huge difference. right?. lets sort up the differences. and use the top k-1 differences to split the array. why k-1 ?? cz with k-1 splits you will get k segments.

for reference, https://codeforces.com/contest/1197/submission/57632604

I don't see why we need a segment tree for E since all queries are suffix queries and all updates are at the position we are currently at. We can just maintain a suffix minimum as we go along.

Solution with editorial's approach minus segment tree: 57644319

So, I actually got hacked on problem A because of exceeded time limit. How do you know if your solution needs to be O(n) or O(nlogn) given the time constraint? Would you just assume 2 seconds means my solution needs to be O(n)?

Sorry for too many questions, I'm just new to CP.

The rule of thumb I use is to plug the maximum input size into the big O, and look for something $$$\le 10^8$$$.

So for $$$n=10^3$$$ for example, $$$O(n^2)$$$ is fine ($$$10^6 < 10^8$$$), but for $$$n=10^5$$$, it'd be too slow ($$$10^{10}>10^8$$$).

In your solution you used quicksort, which is usually $$$O(n \log n)$$$, fast enough, but you were hacked by an input that causes it to become $$$O(n^2)$$$, which is too slow.

Could somebody explain me, if we want to calc T(i, j), we must know colors of r1, r2, r3. But I can't find any mention of it in the tutorial.

Logic behind soulution of C?

I think problem F can be solved simply by reducing the number of states. The number of states that are possible to reach is actually way lower than 64, it's 25. Then I don't think there's any need for optimization, just brute 25^3*1000*log2(10^9) will work. (Correct me if I'm wrong).

In the tutorial for D, last line, you wrote: $$$best_i + sum(i - len, i - 1) - k$$$. But in the code posted below it seems that you are calculating $$$best_i + sum(i + 1, i + len)$$$. I think that is a typo in your tutorial.

Best solution for B. Your text to link here...Can E be solved by Graph Theory? Just saw the "Shortest Path" tag.

There's an edge from i to j with length $$$in_i-out_j$$$ ,if and only if $$$in_i\ge out_j$$$ holds. Sort the matryoshkas by $$$out_i$$$ ,then we can use segment tree to build the graph. To solve the problem more easily,we use two more nodes,S and T. For all node i with indeg=0,add an edge from S to i with length 0. For all node i with outdeg=0,add an edge from i to T with length $$$in_i$$$ . The answer is the number of shortest paths from S to T. Since the graph is a DAG,the solution above works in $$$O(n\log n)$$$ time.

I got an WA on test 8 two days ago.My approach is similar to yours. 57926487

just found my mistake. Thanks anyway.

AC code: 58050060

whats is the idea behind F solution? and is there any easier way to solve F? thanks

Here is an easier $$$O(n \log m)$$$ solution for D:

Let $$$p$$$ be the prefix sum of $$$a$$$. Then maximum cost of subarray ending at $$$i$$$ is $$$ \max_{j < i} \left\lbrace p_i - p_j - k\left \lceil \frac{i - j}{m} \right\rceil\right\rbrace$$$

Main observation is --

So, our formula becomes --

To evaluate the formula quickly, we can keep the maximum of $$$\left\lbrace k\left\lfloor \frac{i}{m} \right\rfloor - p_i\right\rbrace$$$ at index $$$(i\text{ mod } m)$$$ of a segment tree. Which enables us to get the prefix/suffix maximum in $$$O(\log m)$$$ resulting in total complexity $$$O(n \log m)$$$.

the second example of B: 3 1 2. why it is NO？we can move it like this.

-------------------------1------------------1---------------1-------------------------------2

3-1-2 ——> 3-null-2 ——> null-3-2 ——> null-3-2 ——> 1-3-2 ——> 1-3-null ——> finished and yes

Please notice the second condition among the three in the problem statement:

2.pillar i contains

exactly onediskAccording to this, you won't be able to perform your third (also fourth) move.

！！！，all right，thx