393.md (26110B)
1 Source: https://codeforces.com/blog/entry/83942 2 3 Yesterday I saw [this](https://codeforces.com/blog/entry/83811) blog and thought that one bad editorial is better than zero good ones, right? So, enjoy it! 4 5 Here are links to contests: [Div. 1](https://codeforces.com/contest/392), [Div. 2](https://codeforces.com/contest/393) 6 7 Div2A 8 9 **Editorial** 10 11 ### [393A - Nineteen](/contest/393/problem/A "Codeforces Round 230 (Div. 2)") 12 13 Looking at examples and thinking about different cases lead to the idea that the best result would be to build a string which starts with $nineteenineteenineteen...$. The first word $nineteen$ requires 3 letters $n$, 3 letters $e$, 1 letter $i$ and 1 letter $t$. Every next occurrence of $nineteen$ requires the same set of letters, but we need only two letters $n$ for each new word. In other words, we can start with $n$, and then every word will need exactly two extra $n$-s. Let $cnt[c]$ denote the number of characters $c$ in the string. Then the answer is $min\left(\left\lfloor\frac{cnt[n] - 1}{2}\right\rfloor, \,\left\lfloor\frac{cnt[e]}{3}\right\rfloor,\, cnt[i],\, cnt[t]\right)$. (In theory this minimum could be $-\left\lfloor\frac{1}{2}\right\rfloor$, but in C++ it is equal to zero, so everything works fine) 14 15 **Code** 16 17 ``` 18 #include <bits/stdc++.h> 19 20 using namespace std; 21 22 int main() { 23 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 24 25 string s; 26 cin >> s; 27 map<char, int> cnt; 28 for (auto c : s) { 29 cnt[c]++; 30 } 31 cout << min({(cnt['n'] - 1) / 2, cnt['e'] / 3, cnt['i'], cnt['t']}) << '\n'; 32 33 return 0; 34 } 35 ``` 36 37 Div2B 38 39 **Editorial** 40 41 ### [393B - Три матрицы](/contest/393/problem/B "Codeforces Round 230 (Div. 2)") 42 43 We can write this system of equations, using the fact that $B[j][i] = -B[i][j]$ and $A[i][j] = A[j][i]$ 44 45 $ \begin{cases} A[i][j] + B[i][j] = W[i][j]\\ A[j][i] + B[j][i] = W[j][i] \end{cases} \quad\Rightarrow\quad \begin{cases} A[i][j] + B[i][j] = W[i][j]\\ A[i][j] - B[i][j] = W[j][i] \end{cases} $ 46 47 From that, it is easy to conclude that $A[i][j] = \frac{W[i][j] + W[j][i]}{2}$ and $B[i][j] = \frac{W[i][j] - W[j][i]}{2}$. 48 49 By the way, there is some interesting math connected to this problem: [link](https://en.wikipedia.org/wiki/Symmetric_matrix#Decomposition_into_symmetric_and_skew-symmetric) 50 51 **Code** 52 53 ``` 54 #include <bits/stdc++.h> 55 56 using namespace std; 57 58 int main() { 59 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 60 61 int n; 62 cin >> n; 63 vector<vector<double>> w(n, vector<double>(n)); 64 for (int i = 0; i < n; ++i) { 65 for (int j = 0; j < n; ++j) { 66 cin >> w[i][j]; 67 } 68 } 69 70 vector<vector<double>> a(n, vector<double>(n)); 71 vector<vector<double>> b(n, vector<double>(n)); 72 73 for (int i = 0; i < n; ++i) { 74 for (int j = 0; j < n; ++j) { 75 a[i][j] = (w[i][j] + w[j][i]) / 2; 76 b[i][j] = (w[i][j] - w[j][i]) / 2; 77 } 78 } 79 80 for (int i = 0; i < n; ++i) { 81 for (int j = 0; j < n; ++j) { 82 cout << a[i][j] << ' '; 83 } 84 cout << '\n'; 85 } 86 87 for (int i = 0; i < n; ++i) { 88 for (int j = 0; j < n; ++j) { 89 cout << b[i][j] << ' '; 90 } 91 cout << '\n'; 92 } 93 94 return 0; 95 } 96 ``` 97 98 Div2C/Div1A 99 100 **Editorial** 101 102 ### [392A - Заблокированные точки](/contest/392/problem/A "Codeforces Round 230 (Div. 1)") 103 104 Let's look at all pairs of neighboring points such that one of them is special and the other one is not. I claim that it is necessary and sufficient to block at least one point in every such pair 105 106 **Proof** 107 108 Necessity is obvious. Let's prove sufficiency. Assume that we blocked at least one point in each pair, but there are two points $A$ and $B$ such that $A$ is special, $B$ is not and they are 4-connected. Then look at the path between these points. It starts with a special point and ends with non-special. That means that there are two adjacent points in this path such that the first one is special and the second one is not. But it contradicts our statement that we blocked at least one of the points in each pair. 109 110 Now let's look at these pairs. For simplicity, we will look at only $\frac18$-th of a circle. 111 112 **This one** 113 114  115 116 And let's draw all horizontal pairs with a point inside the selected piece. 117 118 **Segments** 119 120  121 122 There are also some vertical segments, but it can be proven with some geometry that the segments on the neighboring horizontal line are either on the same x-coordinate, or one is shifted by one. This means that if we choose the leftmost point in each of these segments, we will cover all vertical pairs as well. 123 124 With some symmetry, this can be done for other pieces of a circle. 125 126 There is only one thing left — we need to bring all pieces together. It is easy when two pieces share a horizontal or vertical line, but in the other case, we need another picture. 127 128 **Picture 1** 129 130  131 132 In this case, everything is already fine, we don't have any "leaks" between parts 133 134 **Picture 2** 135 136  137 138 In that case, we don't have any leaks either, but we have overlapping segments, and that means that we case save 1 point here and 4 points total. 139 140 All we need now is to calculate the number of segments in a circle sector (it is ${n}/\sqrt{2}+1$) and differentiate these two cases. 141 142 **Code** 143 144 ``` 145 #include <bits/stdc++.h> 146 147 using namespace std; 148 149 int main() { 150 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 151 152 long long n; 153 cin >> n; 154 155 if (n == 0) { 156 cout << 1 << '\n'; 157 return 0; 158 } 159 160 int L = sqrt(n * n / 2); 161 162 pair<long long, long long> near = {L + 1, L}; 163 164 int ans = (L * 2 + 1) * 4; 165 166 if (near.first * near.first + near.second * near.second > n * n) 167 ans -= 4; 168 169 cout << ans << '\n'; 170 171 return 0; 172 } 173 ``` 174 175 Div2D/Div1B 176 177 **Editorial** 178 179 ### [392B - Ханойская башня](/contest/392/problem/B "Codeforces Round 230 (Div. 1)") 180 181 First, understand [this solution](https://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution) of the standard Hanoi puzzle, if you don't know it. I will use the same idea to solve this problem. Let's create a function $calc(from, to, n)$ which will count the minimal cost to move $n$ disks from $from$ to $to$. If $n=1$ then we either move the disk directly to $to$, or we first move it to the $mid$ (the remaining rod) and only then move to $to$. If $n \gt 1$ then again, there are two possible strategies. Either we use moves from standard solution — move $n-1$ disks to $mid$, move 1 disk from $from$ to $to$, then move $n-1$ disks to $to$. Or we can make more moves but possibly with less cost: move $n-1$ disks to $to$, then 1 disk from $from$ to $mid$, then $n-1$ disks back to $from$, then 1 disk to $to$, and finally $n-1$ disks to $to$. Here are pictures for both cases: 182 183 **Case 1** 184 185  186 187 [Better resolution](https://imgur.com/a/0fcc8YV) 188 189 **Case 2** 190 191  192 193 [Better resolution](https://imgur.com/6ItXSCl) 194 195 For moving $n-1$ disks we will make recursive calls. If we just do that, we will have an exponential solution, which is not very nice. But we only have $3\times 2 \times n $ different calls — 3 options for $from$, 2 for $to$ and $n$. That means that we can just store every value which we already counted (or I can say a fancy word *memoization*, which means the same thing) 196 197 **Code** 198 199 ``` 200 #include <bits/stdc++.h> 201 202 using namespace std; 203 204 #define ll long long 205 206 array<array<ll, 3>, 3> t; 207 map<pair<pair<int, int>, ll>, ll> mem; 208 209 ll calc(int from, int to, int n) { 210 auto p = make_pair(make_pair(from, to), n); 211 if (mem.count(p)) 212 return mem[p]; 213 int mid = 3 - from - to; 214 if (n == 1) { 215 return mem[p] = min(t[from][mid] + t[mid][to], t[from][to]); 216 } 217 return mem[p] = min(calc(from, mid, n - 1) + t[from][to] + calc(mid, to, n - 1), 218 calc(from, to, n - 1) + t[from][mid] + calc( to, from, n - 1) + t[mid][to] + calc(from, to, n - 1)); 219 } 220 221 int main() { 222 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 223 224 for (int i = 0; i < 3; ++i) { 225 for (int j = 0; j < 3; ++j) { 226 cin >> t[i][j]; 227 } 228 } 229 230 int n; 231 cin >> n; 232 233 cout << calc(0, 2, n) << '\n'; 234 235 return 0; 236 } 237 ``` 238 239 Div2E/Div1C 240 241 **Editorial** 242 243 ### [392C - Еще одна последовательность чисел](/contest/392/problem/C "Codeforces Round 230 (Div. 1)") 244 245 This is obviously some matrix-exponentiation problem. We just have to figure out the matrix. Well, let's look at what we have 246 247 $ A_i(k) = F_i \cdot i^k = (F_{i-1} + F_{i-2}) \cdot i^k = F_{i-1}\cdot ((i-1)+1)^k + F_{i-2}\cdot ((i-2) + 2)^k =\\= \sum_{j=0}^k \binom{k}{j} F_{i-1}(i-1)^j + \sum_{j=0}^k \binom{k}{j} F_{i-2}(i-2)^j\cdot 2^{k-j}=\\= \sum_{j=0}^k \binom{k}{j} A_{i-1}(j) + \sum_{j=0}^k \binom{k}{j} A_{i-2}(j)\cdot 2^{k-j} $ 248 249 Then we just have to store $A_{i-1}(j)$ and $A_{i-2}(j)$ for every $j \in [0;k]$. And also we have to store the sum, so the matrix will be of size $2(k+1)+1$, resulting in $O(k^3\log n)$ in total. 250 251 If you need more information about matrix exponentiation, consider watching the video from Errichto. Oh, and I almost forgot. He says *exponentation* instead of *exponentiation*. Now you will not able to forget this, enjoy! Here is the [link](https://www.youtube.com/watch?v=eMXNWcbw75E) :) (Errichto, no offence, if you are reading this :) ) 252 253 **Code** 254 255 ``` 256 #include <bits/stdc++.h> 257 258 using namespace std; 259 260 #define ll long long 261 262 template<auto P> 263 struct Modular { 264 using value_type = decltype(P); 265 value_type value; 266 267 Modular(ll k = 0) : value(norm(k)) {} 268 269 Modular<P>& operator += (const Modular<P>& m) { value += m.value; if (value >= P) value -= P; return *this; } 270 Modular<P> operator + (const Modular<P>& m) const { Modular<P> r = *this; return r += m; } 271 272 Modular<P>& operator -= (const Modular<P>& m) { value -= m.value; if (value < 0) value += P; return *this; } 273 Modular<P> operator - (const Modular<P>& m) const { Modular<P> r = *this; return r -= m; } 274 Modular<P> operator - () const { return Modular<P>(-value); } 275 276 Modular<P>& operator *= (const Modular<P> &m) { value = value * 1ll * m.value % P; return *this; } 277 Modular<P> operator * (const Modular<P>& m) const { Modular<P> r = *this; return r *= m; } 278 279 Modular<P>& operator /= (const Modular<P> &m) { return *this *= m.inv(); } 280 Modular<P> operator / (const Modular<P>& m) const { Modular<P> r = *this; return r /= m; } 281 282 Modular<P>& operator ++ () { return *this += 1; } 283 Modular<P>& operator -- () { return *this -= 1; } 284 Modular<P> operator ++ (int) { Modular<P> r = *this; r += 1; return r; } 285 Modular<P> operator -- (int) { Modular<P> r = *this; r -= 1; return r; } 286 287 bool operator == (const Modular<P>& m) const { return value == m.value; } 288 bool operator != (const Modular<P>& m) const { return value != m.value; } 289 290 value_type norm(ll k) { 291 if (!(-P <= k && k < P)) k %= P; 292 if (k < 0) k += P; 293 return k; 294 } 295 296 Modular<P> inv() const { 297 value_type a = value, b = P, x = 0, y = 1; 298 while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); } 299 return Modular<P>(x); 300 } 301 }; 302 303 template<auto P> Modular<P> pow(Modular<P> m, ll p) { 304 Modular<P> r(1); 305 while (p) { 306 if (p & 1) r *= m; 307 m *= m; 308 p >>= 1; 309 } 310 return r; 311 } 312 313 template<auto P> ostream& operator << (ostream& o, const Modular<P> &m) { return o << m.value; } 314 template<auto P> istream& operator >> (istream& i, Modular<P> &m) { ll k; i >> k; m.value = m.norm(k); return i; } 315 template<auto P> string to_string(const Modular<P>& m) { return to_string(m.value); } 316 317 using Mint = Modular<1000000007>; 318 // using Mint = Modular<998244353>; 319 // using Mint = long double; 320 321 vector<vector<Mint>> operator * (vector<vector<Mint>> a, vector<vector<Mint>> b) { 322 vector<vector<Mint>> c(a.size(), vector<Mint>(b[0].size(), 0)); 323 for (int i = 0; i < a.size(); ++i) { 324 for (int j = 0; j < a[0].size(); ++j) { 325 for (int k = 0; k < b[0].size(); ++k) { 326 c[i][k] += a[i][j] * b[j][k]; 327 } 328 } 329 } 330 return c; 331 } 332 333 vector<vector<Mint>> pow(vector<vector<Mint>> a, ll p) { 334 vector<vector<Mint>> res(a.size(), vector<Mint>(a.size(), 0)); 335 for (int i = 0; i < res.size(); ++i) { 336 res[i][i] = 1; 337 } 338 while (p) { 339 if (p & 1) { 340 res = res * a; 341 } 342 a = a * a; 343 p /= 2; 344 } 345 return res; 346 } 347 348 int main() { 349 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 350 351 ll n; 352 cin >> n; 353 int k; 354 cin >> k; 355 356 vector<vector<Mint>> mt((k + 1) * 2 + 1, vector<Mint>((k + 1) * 2 + 1, 0)); 357 358 vector<vector<Mint>> vinit(mt.size(), vector<Mint>(1, 0)); 359 360 // first k+1 elements are for F_{i-1}, next k+1 are for F_{i-2}, the last one is for sum up to A_{i-2} 361 for (int i = 0; i < k + 1; ++i) { 362 vinit[i][0] = 1; 363 vinit[i + k + 1][0] = 0; 364 vinit.back()[0] = 0; 365 } 366 vinit[k + 1][0] = 1; 367 368 vector<vector<Mint>> C(50, vector<Mint>(50, 0)); 369 for (int i = 0; i < C.size(); ++i) { 370 C[0][i] = 0; 371 C[i][0] = 1; 372 } 373 374 for (int i = 1; i < C.size(); ++i) { 375 for (int j = 1; j < C.size(); ++j) { 376 C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; 377 } 378 } 379 380 vector<Mint> p2(50, 1); 381 for (int i = 1; i < p2.size(); ++i) 382 p2[i] = p2[i - 1] * 2; 383 384 for (int p = 0; p < k + 1; ++p) 385 mt[k + 1 + p][p] = 1; 386 mt.back().back() = 1; 387 mt.back()[k] = 1; 388 389 for (int p = 0; p < k + 1; ++p) { 390 for (int j = 0; j <= p; ++j) { 391 mt[p][j] += C[p][j]; 392 mt[p][k + 1 + j] += C[p][j] * p2[p - j]; 393 } 394 } 395 396 auto res = pow(mt, n) * vinit; 397 cout << res.back()[0] << '\n'; 398 399 return 0; 400 } 401 ``` 402 403 Div1D 404 405 **Editorial** 406 407 ### [392D - Три массива](/contest/392/problem/D "Codeforces Round 230 (Div. 1)") 408 409 Let forget about $a$ for a minute and solve the problem for two arrays. Of course, it can be done with something like two pointers, but it is not extendable to three arrays (at least I don't know how). We need a more general approach. First, let's assume that $b$ has all elements, which $c$ contains. We can achieve that by copying $c$ at the end of $b$ (it is easy to see that this will not improve the answer). 410 411 Suppose for some number $k$ it has only one occurrence in $b$ and only one in $c$. And $b[i] = c[j] = k$. Then we denote $pos[i] = j$. Now, if $k$ has multiple occurrences in $c$, we will take the smallest $j$. If it has multiple occurrences in $b$, we will set the first $pos[i]$ to $j$ and others to $0$. Why that? Good question. Now the answer for the problem is $min_i((i-1) + max_{j \gt i}pos[j])$. The expression in the brackets corresponds to the case when we take $i$ first elements from $b$. Then we look for all other elements ($j \gt i$) and choose the shortest prefix of $c$ which contains all these elements. That explains why we write the first occurrence of $k$ in $c$ to $pos$. And we fill other values with zero because we don't need them if we already took the first occurrence in $b$. 412 413 Now get $a$ back. What changes if we have some numbers in $a$? Well, in that case, we can set $pos[i]=0$ for all occurrences of that number in $b$ (not only all except first). That means that if we iterate over prefix of $a$ from $0$ to $n$ then we will have to change some $pos$ to zero. But I prefer changing zeros to some values, so we will iterate from $n$ to $0$. 414 415 Well, let's iterate. Suppose we decided not to take prefix of length $i$ in $a$, and instead took prefix of length $i-1$. If there are some occurrences of $a[i]$ before $i$, then nothing changes in $pos$. But if there is no $a[i]$ before $i$, we have to update some $pos$ and recalculate $min_i((i-1) + max_{j \gt i}pos[j])$. I believe there are different structs that can do it, I will describe what I used. 416 417 In the expression, there are maximums on the suffix. They can be stored as pairs $(p, m)$ which means that up to position $p$ maximum on a suffix is at least $m$ (maximum-on-a-suffix is a non-increasing function, obviously). Now, to calculate the answer, we don't have to go through all $i$. We only need to consider such indices $p$ that some pair $(p-1, ?)$ exists in our set. That means that we have to check exactly one option for every pair of adjacent pairs. Remember, we only have to add pairs to this set. And it is easy — add a pair and remove enough pairs before it (while their $m$ less than new $m$). With every addition or removal, we have $O(1)$ additions or removals of options for an answer. Current answers can be stored in a multiset since we only need the minimal value. And if we are looking at a prefix $i$ of $a$, then we have to update the answer with $i$ + (the smallest value from multiset). 418 419 This is probably not the cleanest explanation, so there is a random picture which can help: 420 421 **Picture** 422 423  424 425 *The picture can contain off-by-one error, depending on your indexing and my mistakes*. 426 427 $pos = [1,\,0,\,5,\,3,\,0,\,3,\,2]$. 428 429 The picture illustrates maximums on a suffix for every $i$. In a set, we store one pair for each horizontal segment. When we need to update the answer, we look at all points with a green circle (or actually 1 to the right of these points because in this picture maximum at $x=2$ is $5$, so we need $(3,3)$, not $(2,3)$, but that is exactly what I meant when I said about off-by-one errors). 430 431 **Code** 432 433 ``` 434 #include <bits/stdc++.h> 435 436 using namespace std; 437 438 int main() { 439 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 440 441 int n; 442 cin >> n; 443 vector<int> a(n), b(n), c(n); 444 for (int i = 0; i < n; ++i) 445 cin >> a[i]; 446 for (int i = 0; i < n; ++i) 447 cin >> b[i]; 448 for (int i = 0; i < n; ++i) 449 cin >> c[i]; 450 451 for (auto k : c) { 452 b.push_back(k); 453 } 454 455 map<int, int> whereb; 456 map<int, int> wherec; 457 for (int i = (int)b.size() - 1; i >= 0; --i) 458 whereb[b[i]] = i; 459 for (int i = (int)c.size() - 1; i >= 0; --i) 460 wherec[c[i]] = i; 461 462 vector<bool> first_in_a(a.size(), false); 463 vector<bool> first_in_b(b.size(), false); 464 set<int> ina, inb; 465 for (int i = 0; i < a.size(); ++i) { 466 if (!ina.count(a[i])) { 467 ina.insert(a[i]); 468 first_in_a[i] = true; 469 } 470 } 471 for (int i = 0; i < b.size(); ++i) { 472 if (!inb.count(b[i])) { 473 inb.insert(b[i]); 474 first_in_b[i] = true; 475 } 476 } 477 478 set<pair<int, int>> maxs; 479 multiset<int> res; 480 481 maxs.emplace(1e9, 0); 482 maxs.emplace(-1, 1e9 + 5); 483 res.insert(maxs.begin()->first + next(maxs.begin())->second + 1); 484 485 auto del = [&](pair<int, int> p) { 486 auto it = maxs.find(p); 487 assert(it != maxs.end()); 488 auto inext = next(it); 489 auto iprev = prev(it); 490 491 res.erase(res.find(iprev->first + it->second + 1)); 492 res.erase(res.find(it->first + inext->second + 1)); 493 maxs.erase(it); 494 res.insert(iprev->first + inext->second + 1); 495 }; 496 497 auto add = [&](pair<int, int> p) { 498 auto it = maxs.lower_bound(make_pair(p.first, -5)); 499 if (it->second >= p.second) return; 500 if (it->first == p.first) { 501 ++it; 502 } 503 while (prev(it)->second <= p.second) 504 del(*prev(it)); 505 506 maxs.insert(p); 507 it = maxs.find(p); 508 auto inext = next(it); 509 auto iprev = prev(it); 510 511 res.insert(iprev->first + it->second + 1); 512 res.insert(it->first + inext->second + 1); 513 res.erase(res.find(iprev->first + inext->second + 1)); 514 }; 515 516 for (int i = 0; i < b.size(); ++i) { 517 if (first_in_b[i] && !ina.count(b[i])) { 518 int inc = 1e9; 519 if (wherec.count(b[i])) 520 inc = wherec[b[i]] + 1; 521 add({i, inc}); 522 } 523 } 524 525 int ans = n + *res.begin(); 526 527 for (int i = n - 1; i >= 0; --i) { 528 if (first_in_a[i]) { 529 if (!inb.count(a[i])) break; 530 int inc = 1e9; 531 if (wherec.count(a[i])) 532 inc = wherec[a[i]] + 1; 533 add({whereb[a[i]], inc}); 534 } 535 ans = min(ans, i + *res.begin()); 536 } 537 538 cout << ans << '\n'; 539 540 return 0; 541 } 542 ``` 543 544 Div1E 545 546 **Editorial** 547 548 ### [392E - Удаляем подстроки](/contest/392/problem/E "Codeforces Round 230 (Div. 1)") 549 550 There will be three different $dp$, let's get that out of the way. I wanted to make $4$, but in the end decided to merge two of them. 551 552 Also, before everything, let's update $v$ with $v[i] = max_j(v[j] + v[i - j])$. Because sometimes we want to remove segment of length $5$, but $2 + 3$ gives more points. 553 554 First, let's discuss what a *good* substring is. It is either increasing, decreasing, or increasing up to something and then decreasing. And in any case, the difference between neighboring elements is exactly 1. 555 556 $dp\_mon[l][r]$ — the biggest score we can get from segment $[l;r]$ if in the end we are left with monotonous sequence, starting from $w[l]$ and ending with $w[r]$ (that means that we cannot remove $w[l]$ or $w[r]$). If we can't do that, $dp\_mon[l][r] = -\infty$. 557 558 $dp\_all[l][r]$ — the biggest score we can get from removing the whole segment $[l;r]$. 559 560 $dp[l][r]$ — the best score we can get on segment $[l;r]$ (no restrictions). 561 562 The answer will be $dp[1][n]$. 563 564 When we have these $dp$, it is not very hard to calculate them. To get $dp\_mon[l][r]$ we either have to remove everything in between (if $|w[l] - w[r]| = 1$), or for each number between $l$ and $r$ check if it can be in that monotonous sequence, and if it can, split by this number and add two $dp\_mon[l][j] + dp\_mon[j][r]$ (with intersection, yes). 565 566 Now $dp\_all$. First, let's update it with every $dp\_all[l][j] + dp\_all[j + 1][r]$. Now suppose there is an option, where we can't split the segment into two pieces. Consider the last segment we removed. It is some subsequence of our $[l;r]$ segment. Elements of that subsequence split this segment into pieces. Each of these pieces is independent of each other. That means that if the first element of the subsequence is $w[j]$ then $[l; j-1]$ and $[j; r]$ are independent and we already updated the answer with the sum of $dp\_all$, and similarly with $r$. There is one case, though. When this subsequence starts at $w[l]$ and ends in $w[r]$. But that's what we have $dp\_mon$ for! Now for every element on $[l;r]$ we have to check if this subsequence is increasing from $w[l]$ to $w[j]$ and then decreasing from $w[j]$ to $w[r]$. That means that we add two $dp\_mon$ and after that remove this subsequence with a score of $v[len\_of\_subsequence]$. The length can be calculated from $|w[l] - w[j]|$ and $|w[j] - w[r]|$. 567 568 The last is $dp$. That's the easiest one. Either we remove everything — this is $dp\_all$, or there is some element which we decided not to remove. Then, as discussed in previous paragraph, it is enough to update $dp[l][r]$ by every $dp[l][j] + dp[j + 1][r]$. 569 570 And I know that probably some of $dp$ are useless, but I feel like it is easier to understand the solution with multiple $dp$ with different purposes. 571 572 **Code** 573 574 ``` 575 #include <bits/stdc++.h> 576 577 using namespace std; 578 579 #define ll long long 580 581 const int inf = 1e9; 582 583 int main() { 584 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 585 586 int n; 587 cin >> n; 588 vector<int> v(n); 589 for (int i = 0; i < n; ++i) { 590 cin >> v[i]; 591 } 592 593 v.insert(v.begin(), 0); 594 for (int i = 1; i <= n; ++i) { 595 for (int j = 1; j < i; ++j) { 596 v[i] = max(v[i], v[j] + v[i - j]); 597 } 598 } 599 600 vector<int> w(n); 601 for (int i = 0; i < n; ++i) { 602 cin >> w[i]; 603 } 604 605 auto getv = [&](int ln) { 606 if (ln < v.size()) return v[ln]; 607 return -inf; 608 }; 609 610 vector<vector<ll>> dp_all(n, vector<ll>(n, -inf)); 611 vector<vector<ll>> dp_mon(n, vector<ll>(n, -inf)); 612 vector<vector<ll>> dp(n, vector<ll>(n, 0)); 613 614 for (int i = 0; i < n; ++i) { 615 dp_mon[i][i] = 0; 616 dp_all[i][i] = v[1]; 617 if (i != 0) 618 dp_all[i][i - 1] = 0; 619 } 620 621 for (int k = 1; k <= n; ++k) { 622 for (int l = 0; l < n; ++l) { 623 int r = l + k - 1; 624 if (r >= n) break; 625 626 for (int j = l + 1; j <= r; ++j) { 627 dp_all[l][r] = max(dp_all[l][r], dp_all[l][j - 1] + dp_all[j][r]); 628 } 629 630 if (w[l] != w[r]) { 631 if (abs(w[l] - w[r]) == 1) { 632 dp_mon[l][r] = dp_all[l + 1][r - 1]; 633 } else { 634 for (int j = l + 1; j < r; ++j) { 635 if (w[l] != w[j] && w[r] != w[j] && ((w[l] < w[j]) == (w[j] < w[r]))) { 636 dp_mon[l][r] = max(dp_mon[l][r], dp_mon[l][j] + dp_mon[j][r]); 637 } 638 } 639 } 640 } 641 642 for (int j = l; j <= r; ++j) 643 if (w[j] >= w[l] && w[j] >= w[r]) 644 dp_all[l][r] = max(dp_all[l][r], dp_mon[l][j] + dp_mon[j][r] + getv(abs(w[l] - w[j]) + abs(w[j] - w[r]) + 1)); 645 646 dp[l][r] = max(dp[l][r], dp_all[l][r]); 647 for (int j = l + 1; j <= r; ++j) 648 dp[l][r] = max(dp[l][r], dp[l][j - 1] + dp[j][r]); 649 } 650 } 651 652 cout << dp[0][n - 1] << '\n'; 653 654 return 0; 655 } 656 ``` 657 658 This is my first editorial (and first blog too), so any suggestions, improvements, etc are welcome.