codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1875.md (35813B)


      1 Source: https://codeforces.com/blog/entry/120943
      2 
      3 ## [1875A - Jellyfish and Undertale](/contest/1875/problem/A "Codeforces Round 901 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 We can use one tool each time the timer reaches to $1$, then the answer will be $\sum_{i=1}^n \min(a - 1, x_i) + b$. This can prove to be optimal. Because for each tool, if we use it when the timer is $c$, its contribution to the answer is $\min(x_i, a - c)$. We can't use the tool when the timer is less than or equal to $0$ because the bomb will explode before that, so $c=1$ is the optimal.
      8 
      9 Time complexity: $O(n)$ per test case.
     10 
     11 Memory complexity: $O(1)$ per test case.
     12 
     13 **Code**
     14 
     15 ```
     16 #include<bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int n = 0, a = 0, b = 0;
     21 long long ans = 0;
     22 
     23 inline void solve(){
     24 	scanf("%d %d %d", &a, &b, &n);
     25 	ans = b;
     26 	for(int i = 0, x = 0 ; i < n ; i ++){
     27 		scanf("%d", &x);
     28 		ans += min(a - 1, x);
     29 	}
     30 	printf("%lld\n", ans);
     31 }
     32 
     33 int T = 0;
     34 
     35 int main(){
     36 	scanf("%d", &T);
     37 	for(int i = 0 ; i < T ; i ++) solve();
     38 	return 0;
     39 }
     40 ```
     41 
     42 ## [1874A - Jellyfish and Game](/contest/1874/problem/A "Codeforces Round 901 (Div. 1)")
     43 
     44 **Tutorial**
     45 
     46 Let us define $\min(a)$ to be the minimum value of $a$ in the current round, $\max(a)$ to be the maximum value of $a$ in the current round, $\min(b)$ to be the minimum value of $b$ in the current round, $\max(b)$ to be the maximum value of $b$ in the current round, $\text{MIN}$ to be the minimum value of all the apples, $\text{MAX}$ to be the maximum value of all the apples.
     47 
     48 By greedy and induction, we would come to the following conclusion:
     49 
     50 * If Jellyfish is the one operating this round: If $\min(a) \lt \max(b)$, she will swap this two apples, otherwise she will do nothing.
     51 * If Gellyfish is the one operating this round: If $\max(a) \gt \min(b)$, he will swap this two apples, otherwise she will do nothing.
     52 
     53 We consider who $\text{MAX}$ and $\text{MIN}$ will belong to after the first round.
     54 
     55 In the first round:
     56 
     57 * If $\max(a) \lt \max(b)$, $\text{MAX} = \max(b)$. And because $\min(a) \lt \max(b)$, Jellyfish will swap this two apples. So $\text{MAX}$ belongs to Jellyfish.
     58 * If $\max(a) \gt \max(b)$, $\text{MAX} = \max(a)$. If $\min(a)=\max(a)$, then $\min(a) \gt \max(b)$, Jellyfish will do nothing. Otherwise Jellyfish won't swap the apple with value $\text{MAX}$. In conclusion $\text{MAX}$ belongs to Jellyfish
     59 
     60 We can also show that $\text{MIN}$ belongs to Gellyfish, and the proof is symmetric with the above.
     61 
     62 So in the second round, $\min(b) = \text{MIN}, \max(a) = \text{MAX}$, We have $\text{MIN} \lt \text{MAX}$. So Gellyfish will swap this two apples, in the third round, $\min(a)=\text{MIN}, \max(b) = \text{MAX}$, Jellyfish will swap this two apples.
     63 
     64 So after the first round, the game will go two rounds at a time, with two people swapping two apples with the minimum value and the maximum value back and forth.
     65 
     66 So we only need to know the answer for $k = 1$ and $k = 2$.
     67 
     68 Time complexity: $O(n + m)$ per test case.
     69 
     70 Memory complexity: $O(n + m)$ per test case.
     71 
     72 **Code**
     73 
     74 ```
     75 #include<bits/stdc++.h>
     76 
     77 using namespace std;
     78 
     79 const int N = 1000 + 5;
     80 int n = 0, m = 0, k = 0, x = 0, y = 0, a[N] = {}, b[N] = {};
     81 
     82 inline void solve(){
     83 	scanf("%d %d %d", &n, &m, &k); k --;
     84 	for(int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);
     85 	for(int i = 0 ; i < m ; i ++) scanf("%d", &b[i]);
     86 	x = y = 0;
     87 	for(int i = 1 ; i < n ; i ++) if(a[i] < a[x]) x = i;
     88 	for(int i = 1 ; i < m ; i ++) if(b[i] > b[y]) y = i;
     89 	if(b[y] > a[x]) swap(a[x], b[y]);
     90 	if(k & 1){
     91 		x = 0, y = 0;
     92 		for(int i = 1 ; i < n ; i ++) if(a[i] > a[x]) x = i;
     93 		for(int i = 1 ; i < m ; i ++) if(b[i] < b[y]) y = i;
     94 		swap(a[x], b[y]);
     95 	}
     96 	long long ans = 0;
     97 	for(int i = 0 ; i < n ; i ++) ans += a[i];
     98 	printf("%lld\n", ans);
     99 	
    100 }
    101 
    102 int T = 0;
    103 
    104 int main(){
    105 	scanf("%d", &T);
    106 	for(int i = 0 ; i < T ; i ++) solve();
    107 	return 0;
    108 }
    109 ```
    110 
    111 ## [1875C - Jellyfish and Green Apple](/contest/1875/problem/C "Codeforces Round 901 (Div. 2)")
    112 
    113 **Tutorial**
    114 
    115 Firstly, if $n \geq m$, we can make the problem transform $n \lt m$ by giving each person an apple at a time until there are not enough apples.
    116 
    117 We can calculate the mass of apples that each person ends up with as $\frac n m$.
    118 
    119 Since it's cut in half every time, if $\frac m {\gcd(n, m)}$ is not an integral power of $2$, there's no solution.
    120 
    121 Since the number of apple pieces is added to exactly $1$ for each cut, So we just need to minimize the final number of apple pieces.
    122 
    123 As the problem is transformed, $\frac n m$ is less than $1$, and $\frac m {\gcd(n, m)}$ is an integral power of $2$. So we can uniquely find a set of positive integers $S$ satisfying $\frac n m = \sum_{i \in S} \frac 1 {2^i}$. And this method can be proven to be optimal, if we find another multiset $T$ satisfying $S \neq T$, for every element $x$ that appears twice or more, We can make the answer better by removing two $x$ at a time from $T$ and adding one $x - 1$ to $T$. By repeating this process, eventually $T$ will become $S$.
    124 
    125 We can use $\text{std::__builtin_popcount()}$ to get $|S|$, the answer is $m \times |S|-n$.
    126 
    127 Time complexity: $O(\log m)$ per test case.
    128 
    129 Memory complexity: $O(1)$ per test case.
    130 
    131 **Code**
    132 
    133 ```
    134 #include<bits/stdc++.h>
    135 
    136 using namespace std;
    137 
    138 int n = 0, m = 0;
    139 
    140 inline void solve(){
    141 	scanf("%d %d", &n, &m); n %= m;
    142 	int a = n / __gcd(n, m), b = m / __gcd(n, m);
    143 	if(__builtin_popcount(b) > 1) printf("-1\n");
    144 	else printf("%lld\n", 1ll * __builtin_popcount(a) * m - n);
    145 }
    146 
    147 int T = 0;
    148 
    149 int main(){
    150 	scanf("%d", &T);
    151 	for(int i = 0 ; i < T ; i ++) solve();
    152 	return 0;
    153 }
    154 ```
    155 
    156 ## [1875D - Jellyfish and Mex](/contest/1875/problem/D "Codeforces Round 901 (Div. 2)")
    157 
    158 **Tutorial**
    159 
    160 We only care about the operation before $\text{MEX}(a)$ reaches $0$, because after that, $m$ will never change.
    161 
    162 **Lemma.** Before $\text{MEX}(a)$ reaches $0$, we will choose a positive integer $x$ at a time that satisfies $x \lt \text{MEX}(a)$, and delete all $x$ from $a$, the $\text{MEX}(a)$ will become $x$.
    163 
    164 **Proof.** Because if $x \gt \text{MEX}(a)$, we can place this operation after the $\text{MEX}(a)$ becomes $0$, if we don't delete all of $x$, $\text{MEX}(a)$ won't change, we can also put this operation later.
    165 
    166 So before $\text{MEX}(a)$ reaches $0$, the $x$ we delete is non-increasing.
    167 
    168 It means we can solve this problem by dynamic programming. Let $dp_i$ represents when $\text{MEX}(a)=i$, and we haven't delete any $x$ satisfying $x \lt i$,the minimum value of $m$.
    169 
    170 Let $c_i$ represents the number of times $i$ appears in $a$, the transition is: $\forall j \lt i, dp_j \leftarrow dp_i + i \times (c_j - 1) + j$.
    171 
    172 Time complexity: $O(n^2)$ per test case.
    173 
    174 Memory complexity: $O(n)$ per test case.
    175 
    176 **Code**
    177 
    178 ```
    179 #include<bits/stdc++.h>
    180 
    181 using namespace std;
    182 typedef long long ll;
    183 
    184 const ll N = 5000 + 5, Inf = 0x3f3f3f3f3f3f3f3f;
    185 ll n = 0, m = 0, a[N] = {}, dp[N] = {};
    186 
    187 inline void init(){
    188 	for(ll i = 0 ; i <= n ; i ++) a[i] = 0, dp[i] = Inf;
    189 	n = m = 0;
    190 }
    191 
    192 inline void solve(){
    193 	scanf("%lld", &n);
    194 	for(ll i = 1, x = 0 ; i <= n ; i ++){
    195 		scanf("%lld", &x);
    196 		if(x < n) a[x] ++;
    197 	}
    198 	while(a[m]) m ++;
    199 	dp[m] = 0;
    200 	for(ll i = m ; i >= 1 ; i --) for(ll j = 0 ; j < i ; j ++) dp[j] = min(dp[j], dp[i] + i * a[j]);
    201 	printf("%lld\n", dp[0] - m);
    202 }
    203 
    204 ll T = 0;
    205 
    206 int main(){
    207 	memset(dp, 0x3f, sizeof(dp));
    208 	scanf("%lld", &T);
    209 	for(ll i = 0 ; i < T ; i ++) init(), solve();
    210 	return 0;
    211 }
    212 ```
    213 
    214 ## [1874B - Jellyfish and Math](/contest/1874/problem/B "Codeforces Round 901 (Div. 1)")
    215 
    216 **Tutorial**
    217 
    218 First of all, since $\text{and}, \text{or}, \text{xor}$ are all bitwise operations, each bit is independent of the other.
    219 
    220 We define $a_i$ as the $i$-th bit of $a$, $b_i$ as the $i$-th bit of $b$, $c_i$ as the $i$-th bit of $c$, $d_i$ as the $i$-th bit of $d$, $m_i$ as the $i$-th bit of $m$, $x_i$ as the $i$-th bit of $x$, $y_i$ as the $i$-th bit of $y$. (in binary)
    221 
    222 **Lemma.** For all $i \neq j$, if $(a_i, b_i, m_i) = (a_j, b_j, m_j)$ and $(c_i, d_i) \neq (c_j, d_j)$, the goal cannot be achieved.
    223 
    224 **Proof.** Because after every operation we will have $(x_i, y_i) = (x_j, y_j)$, so we can't achieve he goal.
    225 
    226 Since $(a_i, b_i, m_i)$ has only $2^3=8$ cases, and $(c_i, d_i)$ has only $2^2=4$ cases, and there are some $(0/1, 0/1, 0/1)$ that do not appear in $\{(a_i, b_i, m_i)\ |\ 0 \leq i \leq \log \max(a, b, c, d, m)\}$, so there are only $(4+1)^8 \lt 4\times 10^5$ cases in this problem. We can use BFS(breadth-first search) for preprocessing.
    227 
    228 Time complexity: $O(5^8)$ for preprocessing and $O(\log \max(a, b, c, d, m))$ per test case.
    229 
    230 Memory complexity: $O(5^8)$ for preprocessing and $O(1)$ per test case.
    231 
    232 **Code**
    233 
    234 ```
    235 #include<bits/stdc++.h>
    236 
    237 using namespace std;
    238 
    239 const int S = 4e5 + 5, Inf = 0x3f3f3f3f;
    240 int pw5[10] = {}, dp[S] = {};
    241 queue<int> Q;
    242 
    243 inline void checkmin(int &x, int y){
    244 	if(y < x) x = y;
    245 }
    246 
    247 inline int w(int mask, int i){
    248 	return (mask / pw5[i]) % 5;
    249 }
    250 
    251 inline int f(int a, int b, int m){
    252 	return (a << 2) | (b << 1) | m;
    253 }
    254 
    255 inline int g(int c, int d){
    256 	return (c << 1) | d;
    257 }
    258 
    259 inline int work(int mask, int opt){
    260 	int ret = 0;
    261 	for(int a = 0 ; a < 2 ; a ++) for(int b = 0 ; b < 2 ; b ++) for(int m = 0 ; m < 2 ; m ++){
    262 		int x = w(mask, f(a, b, m)), c = x >> 1, d = x & 1;
    263 		if(opt == 1) c = c & d;
    264 		else if(opt == 2) c = c | d;
    265 		else if(opt == 3) d = c ^ d;
    266 		else d = m ^ d;
    267 		ret += pw5[f(a, b, m)] * g(c, d);
    268 	}
    269 	return ret;
    270 }
    271 
    272 inline void init(){
    273 	pw5[0] = 1;
    274 	for(int i = 1 ; i <= 8 ; i ++) pw5[i] = pw5[i - 1] * 5;
    275 	memset(dp, 0x3f, sizeof(dp));
    276 	int mask = 0;
    277 	for(int a = 0 ; a < 2 ; a ++) for(int b = 0 ; b < 2 ; b ++) for(int m = 0 ; m < 2 ; m ++) mask += pw5[f(a, b, m)] * g(a, b);
    278 	dp[mask] = 0, Q.push(mask);
    279 	while(Q.size()){
    280 		int s = Q.front(); Q.pop();
    281 		for(int opt = 0 ; opt < 4 ; opt ++){
    282 			int t = work(s, opt);
    283 			if(dp[t] == Inf) dp[t] = dp[s] + 1, Q.push(t);
    284 		}
    285 	}
    286 	for(int mask = 0 ; mask < pw5[8] ; mask ++) for(int i = 0 ; i < 8 ; i ++) if(w(mask, i) == 4){
    287 		for(int x = 1 ; x <= 4 ; x ++) checkmin(dp[mask], dp[mask - x * pw5[i]]);
    288 		break;
    289 	}
    290 }
    291 
    292 inline void solve(){
    293 	int A = 0, B = 0, C = 0, D = 0, M = 0, mask = pw5[8] - 1;
    294 	scanf("%d %d %d %d %d", &A, &B, &C, &D, &M);
    295 	for(int i = 0 ; i < 30 ; i ++){
    296 		int a = (A >> i) & 1, b = (B >> i) & 1, c = (C >> i) & 1, d = (D >> i) & 1, m = (M >> i) & 1;
    297 		if(w(mask, f(a, b, m)) == 4) mask -= (4 - g(c, d)) * pw5[f(a, b, m)];
    298 		else if(w(mask, f(a, b, m)) != g(c, d)){
    299 			printf("-1\n");
    300 			return;
    301 		}
    302 	}
    303 	printf("%d\n", (dp[mask] < Inf) ? dp[mask] : -1);
    304 }
    305 
    306 int T = 0;
    307 
    308 int main(){
    309 	init();
    310 	scanf("%d", &T);
    311 	for(int i = 0 ; i < T ; i ++) solve();
    312 	return 0;
    313 }
    314 ```
    315 
    316 ## [1874C - Jellyfish and EVA](/contest/1874/problem/C "Codeforces Round 901 (Div. 1)")
    317 
    318 **Tutorial**
    319 
    320 Let's solve this problem by dynamic programming, Let $f_u$ represents the max probability of reaching city $n$ starting from city $u$.
    321 
    322 The problem is how to transition. for city $u$, we assume that there are $d$ roads from city $u$, the $i$-th road from city $u$ is to city $v_i$.
    323 
    324 Let's sort $v$ by using $f_v$ as the keyword, with $v$ with the larger $f_v$ coming first.
    325 
    326 Let's define an array $a$ of $d$ elements equals to $[f_{v_1}, f_{v_2}, \dots, f_{v_d}]$, according to the definition, $a$ is non-increasing.
    327 
    328 That is, next we want to find an optimal solution such that the probability of going to city $v_i$ is $p_i$, maximizing the value of $\sum_{i=1}^d{a_i \times p_i}$.
    329 
    330 **Tips:** the sum of $p_i$ may not be $1$, because it is possible to stay at city $u$ when $d$ is even.
    331 
    332 For two choices of $p$, $p_1$ and $p_2$, Sometimes we can't which is better, for example:
    333 
    334 $p_1 = [0.6, 0.2, 0.2], p_2 = [0.5, 0.5, 0]$
    335 
    336 when $a=[1.0, 0.2, 0.2]$, $p_1$ is better than $p_2$. But when $a = [1.0, 0.8, 0]$, $p_2$ is better than $p_1$.
    337 
    338 **Tips.** In fact, when $d=3$, $p$ has only one choice $[\frac 1 3, \frac 1 3, \frac 1 3]$, the above is just a hypothetical to illustrate the problem.
    339 
    340 So when can we say, $p_1$ is always not worse than $p_2$?
    341 
    342 **Lemma.** If there are two arrays $p_1$ and $p_2$, satisfying $\forall i \leq d, \sum_{j=1}^i{p_1}_j \geq \sum_{j=1}^i{p_2}_j$, $p_1$ is always not worse than $p_2$.
    343 
    344 **Proof.** Let's consider $a_{d+1}$ as $0$ and define $a'_i = a_i - a_{i+1}$, ${p_1'}_i = \sum_{j=1}^i{p_1}_j$ and ${p_2'}_i = \sum_{j=1}^i{p_2}_j$, then $\sum_{i=1}^d a_i \times {p_1}_i = \sum_{i=1}^d a'_i \times {p_1'}_i, \sum_{i=1}^d a_i \times {p_2}_i = \sum_{i=1}^d a'_i \times {p_2'}_i$, Because $a$ is non-increasing, so $a'_i \geq 0$, and we have $\forall i \leq d, {p_1}_i \geq {p_2}_i$, so $\sum_{i=1}^d a_i \times {p_1}_i \geq \sum_{i=1}^d a_i \times {p_2}_i$.
    345 
    346 Now the problem is, there is whether an array $p$ not worse than any other arrays for for all $d$.
    347 
    348 For $d = 1$, $p = [1.0]$ satisfies the condition.
    349 
    350 For $d = 2$, $p = [0.5, 0]$ satisfies the condition.
    351 
    352 What about $d \gt 2$ ? After they choose the roads for the first time, The size of the problem will become $d - 2$.
    353 
    354 For example, when $d = 4$, Let's assume Jellyfish choose $v_1$ for the first time, then there will be $4$ situations:
    355 
    356 1. When Asuka chooses $v_1$ they will go to $v_1$.
    357 2. When Asuka chooses $v_2$, the problem changes into the subproblem with $[v_3, v_4]$.
    358 3. When Asuka chooses $v_3$, the problem changes into the subproblem with $[v_2, v_4]$.
    359 4. When Asuka chooses $v_4$, the problem changes into the subproblem with $[v_2, v_3]$.
    360 
    361 By calculating, $p = [0.25, 0.25, 0.125, 0]$, it also satisfies the condition.
    362 
    363 Let's define $g_k$ as the best array $p$ when $d=k$, $g'_k$ as the the probabilities of going to cities except the city Jellyfish choose for the first time. By recursion, we can get $g'_k$ from $g_{k-2}$. After that, we insert $\frac 1 k$ into $g'_k$, keeping it non-increasing, we will get $g_k$.
    364 
    365 By calculating, we will find $\frac 1 k$ is always the first element in $g_k$. So when $k \gt 2$, we have the following transition:
    366 
    367 * $g_{k, 1} = \frac 1 k$
    368 * $\forall 1 \lt i \leq k, g_{k, i} = g_{k-2, i - 2} \times \frac {i - 2} k + g_{k-2, i - 1} \times \frac {k - i} k$
    369 
    370 In the above we consider $g_{k, x}$ as $0$ for all $x = 0$ or $x \gt k$.
    371 
    372 Because $g_{k-2}$ satisfies the condition, by greedy and induction we can show that $g_k$ satisfies the condition.
    373 
    374 Time complexity: $O(\max(n)^2)$ for preprocessing and $O(m \log n)$ per test case.
    375 
    376 Memory complexity: $O(\max(n)^2)$ for preprocessing and $O(m)$ per test case.
    377 
    378 **Code**
    379 
    380 ```
    381 #include<bits/stdc++.h>
    382 
    383 using namespace std;
    384 
    385 const int N = 5000 + 5;
    386 int n = 5000, m = 0;
    387 vector<vector<int> > G(N), Gx(N);
    388 long double f[N] = {}, g[N][N] = {};
    389 
    390 inline bool cmp(int u, int v){
    391 	return f[u] > f[v];
    392 }
    393 
    394 inline void work(int u){
    395 	if(u == n){
    396 		f[u] = 1.00;
    397 		return;
    398 	}
    399 	sort(G[u].begin(), G[u].end(), cmp);
    400 	int k = G[u].size();
    401 	for(int i = 0 ; i < k ; i ++){
    402 		int v = G[u][i];
    403 		f[u] += f[v] * g[k][i + 1];
    404 	}
    405 }
    406 
    407 inline void init(){
    408 	for(int u = 1 ; u <= n ; u ++){
    409 		f[u] = 0.00;
    410 		G[u].clear(), Gx[u].clear();
    411 	}
    412 	n = m = 0;
    413 }
    414 
    415 inline void solve(){
    416 	scanf("%d %d", &n, &m);
    417 	for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){
    418 		scanf("%d %d", &u, &v);
    419 		if(u != n){
    420 			G[u].push_back(v);
    421 			Gx[v].push_back(u);
    422 		}
    423 	}
    424 	for(int u = n ; u >= 1 ; u --) work(u);
    425 	printf("%.12Lf\n", f[1]);
    426 }
    427 
    428 int T = 0;
    429 
    430 int main(){
    431 	for(int i = 1 ; i <= n ; i += 2) for(int j = 1 ; j <= i ; j ++) g[i][j] = 1.00 / i;
    432 	for(int i = 2 ; i <= n ; i += 2){
    433 		g[i][1] = 1.00;
    434 		for(int j = 1 ; j <= i ; j ++) g[i][j] /= i;
    435 		if(i + 2 <= n) for(int j = 1 ; j <= i ; j ++) g[i + 2][j + 1] += g[i][j] * (i - j + 1), g[i + 2][j + 2] += g[i][j] * j;
    436 	}
    437 	scanf("%d", &T);
    438 	for(int i = 1 ; i <= T ; i ++) init(), solve();
    439 	return 0;
    440 }
    441 ```
    442 
    443 ## [1874D - Jellyfish and Miku](/contest/1874/problem/D "Codeforces Round 901 (Div. 1)")
    444 
    445 **Tutorial**
    446 
    447 Let's assume that $a$ is given. We can use dynamic programming to solve the problem.
    448 
    449 Let's define $f_i$ as the expected number of days Jellyfish needs to reach city $i$ from city $0$.
    450 
    451 We will have:
    452 
    453 * $f_0=0, f_1=1$
    454 * $\forall i \gt 1, f_i=f_{i-1}+1+\frac {a_{i-1}} {a_{i-1}+a_i} \times (f_i - f_{i-2})$
    455 
    456 Let's make it better:
    457 
    458 * $f_i = f_{i-1} + 1 + \frac {a_{i-1}} {a_i} \times (f_{i-1}-f_{i-2}+1)$
    459 
    460 What does this inspire us to do? Let's define $g_i=f_i-f_{i-1}$, then we will get:
    461 
    462 * $g_1=1$
    463 * $\forall i \gt 1, g_i = 1 + \frac {a_{i-1}} {a_i} \times (g_{i-1}+1)$
    464 
    465 By induction, we will find $g_i = 1 + 2 \times \sum_{j=1}^{i-1} \frac {a_j} {a_i}$. According to the definition, $f_n = \sum_{i=1}^n g_n = n + 2 \times \sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$.
    466 
    467 Then we can use dynamic programming to solve the problem itself.
    468 
    469 Let's define $s_i = \sum_{j=1}^i a_j$, then $f_n = n + 2 \times \sum_{i=1}^n \frac{s_{i-1}}{a_i}$.
    470 
    471 Let's define $dp_{i, x}$ as the minimum value of $\sum_{i=1}^n \frac{s_{i-1}}{a_i}$ when $s_i = x$.
    472 
    473 We transit by enumerating the values of $a_{i+1}$, The transition is: $dp_{i+1, x+y} \leftarrow dp_{i, x} + \frac x y$.
    474 
    475 But the time complexity is $O(n m^2)$, how can it becomes faster?
    476 
    477 Let's take a closer look at $\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$. If there exists $i \lt n$ satisfying $a_i \gt a_{i+1}$. We can swap $a_i$ and $a_{i+1}$, the answer will be better! so $a$ is a non-decreasing array, which means $a_i \leq \frac m {n - i + 1}$.
    478 
    479 Because $\sum_{i=1}^n \frac n i$ is $O(n \log n)$, so if we only enumerate the possible values of $a_i$ the time complexity will be $O(m^2 \log m)$.
    480 
    481 Time complexity: $O(m^2 \log m)$
    482 
    483 Memory complexity: $O(nm)$
    484 
    485 **Code**
    486 
    487 ```
    488 #include<bits/stdc++.h>
    489 
    490 using namespace std;
    491 
    492 const int N = 3000 + 5;
    493 const long double Inf = 1e18;
    494 int n = 0, m = 0;
    495 long double dp[N][N] = {};
    496 
    497 int main(){
    498 	scanf("%d %d", &n, &m);
    499 	for(int i = 0 ; i <= n ; i ++) for(int x = 0 ; x <= m ; x ++) dp[i][x] = Inf;
    500 	dp[0][0] = 0.00;
    501 	for(int i = 1 ; i <= n ; i ++) for(int x = 0 ; x <= m ; x ++) for(int y = 1 ; x + y * (n - i + 1) <= m ; y ++) dp[i][x + y] = min(dp[i][x + y], dp[i - 1][x] + 1.00 * x / y);
    502 	printf("%.12Lf", 2 * dp[n][m] + n);
    503 	return 0;
    504 }
    505 ```
    506 
    507 ## [1874E - Jellyfish and Hack](/contest/1874/problem/E "Codeforces Round 901 (Div. 1)")
    508 
    509 **Tutorial**
    510 
    511 Firstly, if $lim \gt \frac {n(n+1)} 2$, the answer will be $0$. So we only need to solve the problem which satisfies $lim \leq \frac{n(n+1)} 2$.
    512 
    513 We can use dynamic programming to solve the problem:
    514 
    515 Let's define $dp_{i, a}$ means the number of the permutations $P$ of $[1, 2, \dots, i]$, satisfying $\mathrm{fun(P)} = a$.
    516 
    517 Since only relative rankings are useful, we have the following transition:
    518 
    519 * $dp_{0, 0} = 1$
    520 * $\forall i \gt 0, dp_{i, a} = \sum_{j=1}^i \binom {i-1} {j-1} \sum_{b=0}^{a - i} dp_{j - 1, b} \times dp_{i - j, a - b - i}$
    521 
    522 The time complexity is $O(n^6)$, because $a \leq \frac {i(i+1)} 2$, how can it becomes faster?
    523 
    524 FFT (Fast Fourier Transform) might come to mind first. If we use FFT instead of enumerating $t$, The time complexity will become $O(n^4 \log n)$. This is not enough because $n$ is large and $10^9+7$ is not a modulus suitable for NTT (Number-theoretic Transform).
    525 
    526 **Tips.** Also, if you use divide and conquer and FFT, The time complexity will be $O(n^3 \text{poly}(\log n))$, but because FFT have a big constant factor, this still can't pass the problem.
    527 
    528 But we can do something similar to what the FFT does. We define $F_i = \sum_{a=1}^{\frac {n(n + 1)} 2} dp_{i, a} \times x^a$, then we will have the following transition:
    529 
    530 * $F_0=1$
    531 * $F_i = x^i \times \sum_{j=1}^i \binom{i - 1}{j - 1} F_{j-1} \times F_{i-j}$
    532 
    533 For all $1 \leq i \leq n$, The degree of $F_i$ won't exceed $\frac {n(n+1)} 2$. So if we have $\frac{n(n+1)} 2 + 1$ points on $F_n$, We can get $F_n$ by in time complexity $O(n^4)$ using Lagrange Interpolation. The only thing we need to do is the dot product of the functions, so the time complexity of the transition is also $O(n^4)$.
    534 
    535 Time complexity: $O(n^4)$
    536 
    537 Memory complexity: $O(n^3)$
    538 
    539 **Code**
    540 
    541 ```
    542 #include<bits/stdc++.h>
    543 
    544 using namespace std;
    545 typedef long long ll;
    546 
    547 const ll N = 200 + 5, Mod = 1e9 + 7;
    548 
    549 inline ll power(ll x, ll y){
    550 	ll ret = 1;
    551 	while(y){
    552 		if(y & 1) ret = ret * x % Mod;
    553 		x = x * x % Mod, y >>= 1;
    554 	}
    555 	return ret;
    556 }
    557 
    558 ll n = 0, k = 0, lim = 0;
    559 ll C[N][N] = {}, pw[N * N][N] = {}, iv[N * N] = {}, ifac[N * N] = {}, dp[N][N * N] = {};
    560 ll a[N * N] = {}, b[N * N] = {}, ans = 0;
    561 
    562 int main(){
    563 	scanf("%lld %lld", &n, &k); lim = n * (n + 1) / 2;
    564 	for(ll i = 0 ; i <= n ; i ++){
    565 		C[i][0] = 1;
    566 		for(ll j = 1 ; j <= i ; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
    567 	}
    568 	ifac[0] = 1;
    569 	for(ll x = 0 ; x <= lim ; x ++){
    570 		pw[x][0] = 1;
    571 		if(x) iv[x] = power(x, Mod - 2), ifac[x] = ifac[x - 1] * iv[x] % Mod;
    572 		for(ll i = 1 ; i <= n ; i ++) pw[x][i] = pw[x][i - 1] * x % Mod;
    573 	}
    574 	for(ll x = 0 ; x <= lim ; x ++) dp[0][x] = 1;
    575 	for(ll i = 1 ; i <= n ; i ++){
    576 		for(ll j = 0 ; j < i ; j ++) for(ll x = 0 ; x <= lim ; x ++) dp[i][x] = (dp[i][x] + dp[j][x] * dp[i - 1 - j][x] % Mod * C[i - 1][j]) % Mod;
    577 		for(ll x = 0 ; x <= lim ; x ++) dp[i][x] = dp[i][x] * pw[x][i] % Mod;
    578 	}
    579 	a[0] = 1;
    580 	for(ll i = 0 ; i <= lim ; i ++){
    581 		for(ll x = lim ; x >= 1 ; x --) a[x] = (a[x - 1] + a[x] * (Mod - i)) % Mod;
    582 		a[0] = a[0] * (Mod - i) % Mod;
    583 	}
    584 	for(ll i = 1 ; i <= lim ; i ++) if(dp[n][i]){
    585 		ll w = dp[n][i] * ifac[i] % Mod * ifac[lim - i] % Mod;
    586 		if((lim - i) & 1) w = Mod - w;
    587 		b[0] = a[0] * (Mod - iv[i]) % Mod;
    588 		for(ll x = 1 ; x <= lim ; x ++) b[x] = (a[x] - b[x - 1] + Mod) * (Mod - iv[i]) % Mod;
    589 		for(ll x = k ; x <= lim ; x ++) ans = (ans + b[x] * w) % Mod;
    590 	}
    591 	printf("%lld\n", ans);
    592 	return 0;
    593 }
    594 ```
    595 
    596 ## [1874F - Jellyfish and OEIS](/contest/1874/problem/F "Codeforces Round 901 (Div. 1)")
    597 
    598 **Tutorial**
    599 
    600 Let's call a section $[l, r]$ bad if $[p_l, p_{l+1}, \dots, p_{r-1}, p_r]$ is a permutation of $[l, l + 1, \dots, r - 1, r]$ and $l \leq r \leq m_l$.
    601 
    602 Let's call a section $[l, r]$ primitive if it's a bad section and there are no section $[l', r']$ satisfying $[l', r']$ is also a bad section and $[l, r]$ covers $[l', r']$.
    603 
    604 **Lemma.** For all primitive sections, none two of them intersect.
    605 
    606 **Proof.** If $[l_1, r_1]$ is a bad section, $[l_2, r_2]$ is a bad section and $l_1 \lt l_2 \lt r_1 \lt r_2$, the section $[l_2, r_1]$ will also be a bad section, but both $[l_1, r_1]$ and $[l_2, r_2]$ covers $[l_2, r_1]$, so $[l_1, r_1]$ and $[l_2, r_2]$ can't be primitive at the same time.
    607 
    608 Let's use the principle of inclusion-exclusion and dynamic programming to solve the problem.
    609 
    610 Let's define $f(l, r)$ as the number of $p_l, p_{l+1}, \dots, p_{r-1}, p_r$ which is a primitive section. By the principle of inclusion-exclusion, we count the ways to fix $k$ primitive sections in range $[l, r]$, and arrange the rest arbitrarily.
    611 
    612 Then we can define $g_{1/2}(l, r, x)$ as the number of ways to fix $k$ ($k$ is odd/even) primitive sections in range $[l, r]$, and the number of the positions which doesn't cover by any primitive section is $x$.
    613 
    614 Finally we define $g(l, r, x) = g_2(l, r, x) - g_1(l, r, x)$, We will have the following transition:
    615 
    616 * $\forall l \leq r \leq m_l, f(l, r) = \sum_{x=0}^{r-l+1} g(l, r, x) \times x! + f(l, r)$
    617 * $g(l, r, x) = g(l, r - 1, x - 1) - \sum_{mid=l}^r g(l, mid - 1, x )\times f(mid, r)$
    618 
    619 **Tips.** In the transition of $f(l, r)$, We add $f(l, r)$ because $f(l, r)$ contributes to $g(l, r, 0)$, but it should not contribute to $f(l, r)$, This problem can be solved by ordering the transitions.
    620 
    621 According to the definition, $\sum_{x=0}^{n} g(1, n, x) \times x!$ is the answer.
    622 
    623 Time complexity: $O(n^4)$
    624 
    625 Memory complexity: $O(n^3)$
    626 
    627 **Code**
    628 
    629 ```
    630 #include<bits/stdc++.h>
    631 
    632 using namespace std;
    633 typedef long long ll;
    634 
    635 const ll N = 200 + 5, Mod = 1e9 + 7;
    636 ll n = 0, m[N] = {}, fac[N] = {}, f[N][N] = {}, g[N][N][N] = {};
    637 
    638 int main(){
    639 	scanf("%lld", &n);
    640 	for(ll i = 1 ; i <= n ; i ++) scanf("%lld", &m[i]);
    641 	if(m[1] == n){
    642 		printf("0");
    643 		return 0;
    644 	}
    645 	fac[0] = 1;
    646 	for(ll i = 1 ; i <= n ; i ++) fac[i] = fac[i - 1] * i % Mod;
    647 	for(ll i = 1 ; i <= n ; i ++) g[i][i - 1][0] = 1;
    648 	for(ll l = n ; l >= 1 ; l --) for(ll r = l ; r <= n ; r ++){
    649 		for(ll x = 1 ; x <= r - l + 1 ; x ++) g[l][r][x] = g[l][r - 1][x - 1];
    650 		for(ll mid = l ; mid < r ; mid ++) if(r <= m[mid + 1]) for(ll x = 0 ; x <= mid - l + 1 ; x ++) g[l][r][x] = (g[l][r][x] + g[l][mid][x] * (Mod - f[mid + 1][r])) % Mod;
    651 		for(ll x = 0 ; x <= r - l + 1 ; x ++) f[l][r] = (f[l][r] + g[l][r][x] * fac[x]) % Mod;
    652 		if(r <= m[l]) g[l][r][0] = (g[l][r][0] + (Mod - f[l][r])) % Mod;
    653 	}
    654 	printf("%lld", f[1][n]);
    655 	return 0;
    656 }
    657 ```
    658 
    659 ## [1874G - Jellyfish and Inscryption](/contest/1874/problem/G "Codeforces Round 901 (Div. 1)")
    660 
    661 **Tutorial**
    662 
    663 For convenience, let's define $k = \max(a, b, x, y)$, use operation 1 for "You will get a card with $a$ HP, and $b$ damage", operation 2 for "If you have at least one card, choose one of your cards and increase its HP by $x$" and operation 3 for "If you have at least one card, choose one of your cards and increase its damage by $y$", operation 4 for "You will get a prop with $w$ power", operation 5 for "You can choose at most one of your cards and multiply its damage by $10^9$", "the $i$-th card" for the card we get from vertex $i$ (It must be operation 1 on vertex $i$), "do operation 2/3/5 onto card $i$" for "When we do this operation 2/3/5, we will choose the card $i$ and increase his HP or damage".
    664 
    665 Let us consider the problem without the operation 5, what's the maximum possible answer. If you want to maximize the the sum of the power of your cards, the answer will not exceeding $(100 \times 200)^2 = 4 \times 10^8$; If you you want to maximize the the sum of the power of your props, the answer will not exceeding $200 \times 10^6 = 2 \times 10^8$. Because $4 \times 10^8 + 2 \times 10^8 = 6 \times 10^8 \lt 10^9$, so the operation $n$ is the most important. Let's called the card we wil do the operation 5 onto it the "flash card". Let's use meet-in-the-middle, the problem is divided into two subproblems — the game before we get the flash card and the game after we get the flash card.
    666 
    667 ### 1. The game after we get the flash card
    668 
    669 It's a easy problem, we can use dynamic programming to solve this problem.
    670 
    671 Since the most important thing is the HP and damage of the flash card, so we define the following dynamic programming state:
    672 
    673 * $dp_b(u, a)$ means we are current at vertex $u$, the current HP of the flash card is $a$, the maximum damage of the flash card.
    674 * $dp_c(u, a)$ means we are current at vertex $u$, the current HP of the flash card is $a$, the damage of the flash card is $dp_b(u, a)$, the maximum sum of the power of all the other cards and props.
    675 
    676 Since $a \leq nk$, the time complexity of the transition is $O(m \times n \times k)$.
    677 
    678 ### 2. The game before we get the flash card
    679 
    680 This is the key of the problem, and since it's much more difficult, we first consider the subproblems of this problem.
    681 
    682 #### I. If the graph is a chain, and all the operation 2 and operation 3 is after the operation 1
    683 
    684 **Lemma.** We will do all the operation 2 onto one of the cards, symmetrically we will also do all the operation 3 onto one of the cards.
    685 
    686 **Proof.** We consider a sequence of operations, let's consider if we do all the operation 1 on the card with the max damage after doing all the operation 2, the answer won't be worse, we can do all the operation 1 onto this card instead, then we make a symmetrical adjustment, the answer won't be worse, and all the operation 2 is done onto one of the cards, all the operation 3 is done onto one of the cards.
    687 
    688 #### II. If the graph is a chain
    689 
    690 It's similar to the **subproblem I**. If we say **subproblem I** is like a "global max value", then **subproblem II** is like a "prefix max value".
    691 
    692 Let's define $p_i$ means we will do the operation 2/3 on vertex $i$ onto the $p_i$-th card.
    693 
    694 **Lemma1.** If there is a operation 2 on vertex $i$ and a operation 2 on vertex $j$, if $p_i \lt j \lt i$, we will have $p_j = p_i$.
    695 
    696 **Proof.** Let's consider the final HP and damage of the cards after all the operations. Because we do the operation 2 on vertex $i$ onto the $p_i$-th card, for all $i' \lt i$, the damage of the $i'$-th card is not larger than the $p_i$-th card. So for $j$, if we don't do the operation 2 on vertex j onto the $p_i$-th card, we can do it onto the $p_i$-th card instead, the answer won't be worse.
    697 
    698 Symmetrically, **Lemma1** is also correct for operation 3.
    699 
    700 Now we can use dynamic programming to solve the problem, we define the following dynamic programming state:
    701 
    702 * $f(u, a, b)$ means we are current at vertex $u$, we will do the next several operation 3 onto a card with $a$ HP after all the operations and we will do the next several operation 2 onto a card with $b$ damage after all the operations, and this two cards are not the same.
    703 * $g(u, a, b)$ means we are current at vertex $u$, We will do the next several operation 2 and operation 3 onto a card currently having $a$ HP and $b$ damage.
    704 
    705 The time complexity is $O(m \times n^2 \times k^2)$, but it's not enough.
    706 
    707 **Lemma2.** If a card has $a$ HP and $b$ damage after all the operations and it's not the flash card, $\min(a, b) \leq k$.
    708 
    709 **Proof.** If we use this card as the flash card instead of the last one, and do all the operations done onto the last flash card onto this card, the power of the flash card will be larger. So it won't exist in this half problem.
    710 
    711 Now the time complexity becomes $O(m \times n \times k^2)$, it's still not enough.
    712 
    713 **Lemma3.** Let's define $A$ as the maximum HP of all the cards except the flash card after all the operations, $B$ as the maximum damage of all the cards except the flash card after all the operations, $\min(A, B) \leq k$.
    714 
    715 **Proof.** Let's assume that the $i$-th card has $A$ HP after all the operations, the $j$-th card has $B$ damage after all the operations and $A \gt k, B \gt k$. If $i = j$, it conflicts with **Lemma 2**; If $i \lt j$, because of the **Lemma 2**, the HP of the $j$-th card after all the operations won't exceed $k$, let's use $A'$ as the HP of the $j$-th card after all the operations, and $B \gt k$, so we have done some operation 3 onto the $j$-th card. But because $A \gt k \geq A'$, if we do these operations onto the $i$-th card, the answer will be better; If $i \gt j$, it's symmetric with $i \lt j$.
    716 
    717 But we can make the dynamic programming state better:
    718 
    719 * $f(u, a, b)$ means we are current at vertex $u$, we will do the next several operation 3 onto a card with $a$ HP after all the operations and we will do the next several operation 2 onto a card with $b$ damage after all the operations, and this two cards are not the same.
    720 * $g_a(u, a, a')$ means we are current at vertex $u$, we will do the next several operation 3 onto a card with $a$ HP after all the operations, we will do the next several operation 2 onto a card and totally increase $a'$ HP in the next several operations to reach it's HP after all the operations.
    721 * $g_b(u, b, b')$ it's symmetric with $g_a$, just swap "HP" and "damage".
    722 
    723 Let's define $A$ as the maximum HP of all the cards except the flash card after all the operations, $B$ as the maximum damage of all the cards except the flash card after all the operations. We will find the $a, a', b, b'$ in $f, g_a, g_b$ is $O(k)$ because if $A \leq k$, using $g_a$ we can get the right answer, if $B \leq k$, using $g_b$ we can get the right answer.
    724 
    725 the time complexity of the transition is $O(m \times k^2)$.
    726 
    727 The transition is very complex, you can see more details in my code : )
    728 
    729 In my code, I use $g(u)$ to make the transition better. When $a'$ or $b'$ reaches $0$, we reaches the vertex $u$ and there is a operation 1 on vertex $u$, I don't enumerate the value of the next $a$ and $b$ while transiting. I transit it to $g(u)$ first, and enumerate the value of the next $a$ and $b$ together.
    730 
    731 #### III. the problem itself
    732 
    733 Since the path is a chain, and we use dynamic programming to solve the problem. There's no difference whether the graph is a chain.
    734 
    735 Time complexity: $O(m(nk+k^2))$
    736 
    737 Memory complexity: $O(n^2k+nk^2)$
    738 
    739 **Code**
    740 
    741 ```
    742 #include<bits/stdc++.h>
    743 
    744 using namespace std;
    745 typedef long long ll;
    746 
    747 const int N = 200 + 5;
    748 const ll lim = 1e9;
    749 
    750 inline void checkmax(int &x, int y){
    751 	if(y > x) x = y;
    752 }
    753 
    754 inline void checkmax(ll &x, ll y){
    755 	if(y > x) x = y;
    756 }
    757 
    758 inline void checkmax(pair<int, int> &x, pair<int, int> y){
    759 	if(y > x) x = y;
    760 }
    761 
    762 int n = 0, m = 0, k = 0, opt[N] = {}, a[N] = {}, b[N] = {}, w[N] = {};
    763 int f[N][N][N] = {}, g[N] = {}, g_a[N][N][N] = {}, g_b[N][N][N] = {};
    764 pair<int, int> dp[N][N * N] = {};
    765 vector<vector<int> > G(N);
    766 
    767 int main(){
    768 	scanf("%d %d", &n, &m);
    769 	for(int u = 1 ; u <= n ; u ++){
    770 		scanf("%d", &opt[u]);
    771 		if(opt[u] == 1) scanf("%d %d", &a[u], &b[u]);
    772 		else if(opt[u] == 2) scanf("%d", &a[u]);
    773 		else if(opt[u] == 3) scanf("%d", &b[u]);
    774 		else if(opt[u] == 4) scanf("%d", &w[u]);
    775 		k = max(k, max(a[u], b[u]));
    776 	}
    777 	for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){
    778 		scanf("%d %d", &u, &v);
    779 		G[u].push_back(v);
    780 	}
    781 	memset(f, -1, sizeof(f));
    782 	memset(g, -1, sizeof(g)), memset(g_a, -1, sizeof(g_a)), memset(g_b, -1, sizeof(g_b));
    783 	memset(dp, -1, sizeof(dp));
    784 	f[1][0][0] = 0;
    785 	for(int u = 1 ; u <= n ; u ++){
    786 		if(opt[u] == 1 && g[u] != -1){
    787 			for(int x = a[u] ; x <= k ; x ++) checkmax(g_a[u][x][x - a[u]], g[u] + x * b[u]);
    788 			for(int x = b[u] ; x <= k ; x ++) checkmax(g_b[u][x][x - b[u]], g[u] + x * a[u]);
    789 			checkmax(dp[u][a[u]], make_pair(b[u], g[u]));
    790 		}
    791 		for(int v : G[u]){
    792 			if(opt[v] == 1){
    793 				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
    794 					if(f[u][x][y] != -1){
    795 						checkmax(f[v][max(x, a[v])][max(y, b[v])], f[u][x][y] + a[v] * b[v]);
    796 						checkmax(g[v], f[u][x][y]);
    797 					}
    798 					if(g_a[u][x][y] != -1){
    799 						checkmax(g_a[v][max(x, a[v])][y], g_a[u][x][y] + a[v] * b[v]);
    800 						if(!y){
    801 							checkmax(g[v], g_a[u][x][y]);
    802 							checkmax(f[v][x][b[v]], g_a[u][x][y] + a[v] * b[v]);
    803 						}
    804 					}
    805 					if(g_b[u][x][y] != -1){
    806 						checkmax(g_b[v][max(x, b[v])][y], g_b[u][x][y] + a[v] * b[v]);
    807 						if(!y){
    808 							checkmax(g[v], g_b[u][x][y]);
    809 							checkmax(f[v][a[v]][x], g_b[u][x][y] + a[v] * b[v]);
    810 						}
    811 					}
    812 				}
    813 				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
    814 					int y = dp[u][x].first, z = dp[u][x].second;
    815 					checkmax(dp[v][x], make_pair(y, z + a[v] * b[v]));
    816 				}
    817 			}
    818 			else if(opt[v] == 2){
    819 				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
    820 					if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + a[v] * y);
    821 					if(g_a[u][x][y] != -1 && y >= a[v]) checkmax(g_a[v][x][y - a[v]], g_a[u][x][y]);
    822 					if(g_b[u][x][y] != -1) checkmax(g_b[v][x][y], g_b[u][x][y] + a[v] * x);
    823 				}
    824 				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
    825 					int y = dp[u][x].first, z = dp[u][x].second;
    826 					checkmax(dp[v][x + a[v]], make_pair(y, z));
    827 				}
    828 			}
    829 			else if(opt[v] == 3){
    830 				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
    831 					if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + x * b[v]);
    832 					if(g_a[u][x][y] != -1) checkmax(g_a[v][x][y], g_a[u][x][y] + x * b[v]);
    833 					if(g_b[u][x][y] != -1 && y >= b[v]) checkmax(g_b[v][x][y - b[v]], g_b[u][x][y]);
    834 				}
    835 				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
    836 					int y = dp[u][x].first, z = dp[u][x].second;
    837 					checkmax(dp[v][x], make_pair(y + b[v], z));
    838 				}
    839 			}
    840 			else{
    841 				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
    842 					if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + w[v]);
    843 					if(g_a[u][x][y] != -1) checkmax(g_a[v][x][y], g_a[u][x][y] + w[v]);
    844 					if(g_b[u][x][y] != -1) checkmax(g_b[v][x][y - b[v]], g_b[u][x][y] + w[v]);
    845 				}
    846 				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
    847 					int y = dp[u][x].first, z = dp[u][x].second;
    848 					checkmax(dp[v][x], make_pair(y, z + w[v]));
    849 				}
    850 			}
    851 		}
    852 	}
    853 	ll ans = f[n][0][0];
    854 	for(int x = 0 ; x <= n * k ; x ++) if(dp[n][x] != make_pair(-1, -1)){
    855 		int y = dp[n][x].first, z = dp[n][x].second;
    856 		checkmax(ans, lim * x * y + z);
    857 	}
    858 	printf("%lld", ans);
    859 	return 0;
    860 }
    861 ```