1304.md (9884B)
1 Source: https://codeforces.com/blog/entry/73934 2 3 [1304A — Two Rabbits](https://codeforces.com/contest/1304/problem/A) 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int main() 16 { 17 int tc; 18 cin >> tc; 19 while (tc--) 20 { 21 int x, y, a, b; 22 cin >> x >> y >> a >> b; 23 cout << ((y - x) % (a + b) == 0 ? (y - x) / (a + b) : -1) << endl; 24 } 25 } 26 ``` 27 28 [1304B — Longest Palindrome](https://codeforces.com/contest/1304/problem/B) 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution** 35 36 ``` 37 #include <bits/stdc++.h> 38 using namespace std; 39 40 const int MAX_N = 100; 41 string s[MAX_N]; 42 43 int main() 44 { 45 set<string> dict; 46 int n, m, i; 47 cin >> n >> m; 48 for (i = 0; i < n; i++) 49 { 50 cin >> s[i]; 51 dict.insert(s[i]); 52 } 53 vector<string> left, right; 54 string mid; 55 for (i = 0; i < n; i++) 56 { 57 string t = s[i]; 58 reverse(t.begin(), t.end()); 59 if (t == s[i]) 60 mid = t; 61 else if (dict.find(t) != dict.end()) 62 { 63 left.push_back(s[i]); 64 right.push_back(t); 65 dict.erase(s[i]); 66 dict.erase(t); 67 } 68 } 69 cout << left.size() * m * 2 + mid.size() << endl; 70 for (string x : left) 71 cout << x; 72 cout << mid; 73 reverse(right.begin(), right.end()); 74 for (string x : right) 75 cout << x; 76 cout << endl; 77 } 78 ``` 79 80 [1304C — Air Conditioner](https://codeforces.com/contest/1304/problem/C) 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution** 87 88 ``` 89 #include <bits/stdc++.h> 90 using namespace std; 91 92 const int MAX_N = 100; 93 94 int t[MAX_N], lo[MAX_N], hi[MAX_N]; 95 96 int main() 97 { 98 int tc; 99 cin >> tc; 100 while (tc--) 101 { 102 int n, m, i; 103 cin >> n >> m; 104 for (i = 0; i < n; i++) 105 cin >> t[i] >> lo[i] >> hi[i]; 106 int prev = 0; 107 int mn = m, mx = m; 108 bool flag = true; 109 for (i = 0; i < n; i++) 110 { 111 mx += t[i] - prev; 112 mn -= t[i] - prev; 113 if (mx < lo[i] || mn > hi[i]) 114 { 115 flag = false; 116 break; 117 } 118 mx = min(mx, hi[i]); 119 mn = max(mn, lo[i]); 120 prev = t[i]; 121 } 122 if (flag) 123 cout << "YES\n"; 124 else 125 cout << "NO\n"; 126 } 127 } 128 ``` 129 130 [1304D — Shortest and Longest LIS](https://codeforces.com/contest/1304/problem/D) 131 132 **Tutorial** 133 134 Tutorial is loading... 135 136 **Solution** 137 138 ``` 139 #include <bits/stdc++.h> 140 using namespace std; 141 142 const int MAX_N = 200000; 143 int ans[MAX_N + 5]; 144 145 int main() 146 { 147 int tc; 148 cin >> tc; 149 while (tc--) 150 { 151 int n, i, j; 152 string s; 153 cin >> n >> s; 154 155 int num = n, last = 0; 156 for (i = 0; i < n; i++) 157 { 158 if (i == n - 1 || s[i] == '>') 159 { 160 for (j = i; j >= last; j--) 161 ans[j] = num--; 162 last = i + 1; 163 } 164 } 165 for (i = 0; i < n; i++) 166 cout << ans[i] << (i == n - 1 ? '\n' : ' '); 167 168 num = 1, last = 0; 169 for (i = 0; i < n; i++) 170 { 171 if (i == n - 1 || s[i] == '<') 172 { 173 for (j = i; j >= last; j--) 174 ans[j] = num++; 175 last = i + 1; 176 } 177 } 178 for (i = 0; i < n; i++) 179 cout << ans[i] << (i == n - 1 ? '\n' : ' '); 180 } 181 } 182 ``` 183 184 [1304E — 1-Trees and Queries](https://codeforces.com/contest/1304/problem/E) 185 186 **Tutorial** 187 188 Tutorial is loading... 189 190 **Solution** 191 192 ``` 193 #include <bits/stdc++.h> 194 using namespace std; 195 196 const int MAX_N = 100000; 197 const int LIM = 17; 198 const int INF = (int)1e9 + 7; 199 200 vector<int> adj[MAX_N + 5]; 201 int depth[MAX_N + 5]; 202 int par[MAX_N + 5][LIM + 1]; 203 204 void build(int cur, int p) 205 { 206 int i; 207 208 depth[cur] = depth[p] + 1; 209 par[cur][0] = p; 210 for (i = 1; i <= LIM; i++) 211 par[cur][i] = par[par[cur][i - 1]][i - 1]; 212 213 for (int x : adj[cur]) 214 if (x != p) 215 build(x, cur); 216 } 217 218 int lca_len(int a, int b) 219 { 220 int i, len = 0; 221 222 if (depth[a] > depth[b]) 223 swap(a, b); 224 for (i = LIM; i >= 0; i--) 225 { 226 if (depth[par[b][i]] >= depth[a]) 227 { 228 b = par[b][i]; 229 len += (1 << i); 230 } 231 } 232 233 if (a == b) 234 return len; 235 for (i = LIM; i >= 0; i--) 236 { 237 if (par[a][i] != par[b][i]) 238 { 239 a = par[a][i]; 240 b = par[b][i]; 241 len += (1 << (i + 1)); 242 } 243 } 244 return len + 2; 245 } 246 247 int main() 248 { 249 ios::sync_with_stdio(false); 250 cin.tie(0); 251 252 int n, q, i; 253 cin >> n; 254 255 for (i = 0; i < n - 1; i++) 256 { 257 int u, v; 258 cin >> u >> v; 259 adj[u].push_back(v); 260 adj[v].push_back(u); 261 } 262 build(1, 0); 263 264 cin >> q; 265 while (q--) 266 { 267 int x, y, a, b, k; 268 cin >> x >> y >> a >> b >> k; 269 int without = lca_len(a, b); 270 int with = min(lca_len(a, x) + lca_len(y, b), lca_len(a, y) + lca_len(x, b)) + 1; 271 int ans = INF; 272 if (without % 2 == k % 2) 273 ans = without; 274 if (with % 2 == k % 2) 275 ans = min(ans, with); 276 cout << (ans <= k ? "YES" : "NO") << '\n'; 277 } 278 } 279 ``` 280 281 [1304F1 — Animal Observation (easy version)](https://codeforces.com/contest/1304/problem/F1) 282 283 **Tutorial** 284 285 Tutorial is loading... 286 287 **Solution** 288 289 ``` 290 #include <bits/stdc++.h> 291 using namespace std; 292 293 const int MAX_N = 50; 294 const int MAX_M = 20000; 295 const int MAX_K = 20; 296 297 int animal[MAX_N + 5][MAX_M + 5]; 298 int psum[MAX_N + 5][MAX_M + 5]; 299 int lmax[MAX_N + 5][MAX_M + 5]; 300 int rmax[MAX_N + 5][MAX_M + 5]; 301 int dp[MAX_N + 5][MAX_M + 5]; 302 303 inline int ps(int i, int j, int k) 304 { 305 return psum[i][k] - psum[i][j - 1]; 306 } 307 308 int main() 309 { 310 ios::sync_with_stdio(false); 311 cin.tie(0); 312 int i, j; 313 314 int n, m, k; 315 cin >> n >> m >> k; 316 for (i = 1; i <= n; i++) 317 { 318 for (j = 1; j <= m; j++) 319 { 320 cin >> animal[i][j]; 321 psum[i][j] = psum[i][j - 1] + animal[i][j]; 322 } 323 } 324 325 for (i = 1; i <= n; i++) 326 { 327 for (j = 1; j <= m - k + 1; j++) 328 { 329 int p = ps(i, j, j + k - 1) + ps(i + 1, j, j + k - 1); 330 if (i == 1) 331 { 332 dp[i][j] = p; 333 continue; 334 } 335 int mx = 0; 336 for (int x = max(1, j - k + 1); x <= min(m - k + 1, j + k - 1); x++) 337 mx = max(mx, dp[i - 1][x] + p - ps(i, max(x, j), min(x + k - 1, j + k - 1))); 338 dp[i][j] = mx; 339 if (j > k) 340 dp[i][j] = max(dp[i][j], lmax[i - 1][j - k] + p); 341 if (j + k - 1 <= m - k) 342 dp[i][j] = max(dp[i][j], rmax[i - 1][j + k] + p); 343 } 344 for (j = 1; j <= m - k + 1; j++) 345 lmax[i][j] = max(lmax[i][j - 1], dp[i][j]); 346 for (j = m - k + 1; j >= 1; j--) 347 rmax[i][j] = max(rmax[i][j + 1], dp[i][j]); 348 } 349 350 cout << *max_element(dp[n] + 1, dp[n] + m + 1) << '\n'; 351 } 352 ``` 353 354 [1304F2 — Animal Observation (hard version)](https://codeforces.com/contest/1304/problem/F2) 355 356 **Tutorial** 357 358 Tutorial is loading... 359 360 **Solution: O(nmlogm)** 361 362 ``` 363 #include <bits/stdc++.h> 364 using namespace std; 365 366 const int MAX_N = 50; 367 const int MAX_M = 20000; 368 const int MAX_K = 20; 369 370 int animal[MAX_N + 5][MAX_M + 5]; 371 int psum[MAX_N + 5][MAX_M + 5]; 372 int dp[MAX_N + 5][MAX_M + 5]; 373 int t[MAX_M * 4], lazy[MAX_M * 4]; 374 375 void update_lazy(int i, int lo, int hi) 376 { 377 if (lazy[i]) 378 { 379 t[i] += lazy[i]; 380 if (lo != hi) 381 { 382 lazy[i * 2] += lazy[i]; 383 lazy[i * 2 + 1] += lazy[i]; 384 } 385 lazy[i] = 0; 386 } 387 } 388 389 int update(int i, int lo, int hi, int l, int r, int val) 390 { 391 update_lazy(i, lo, hi); 392 if (lo > r || hi < l) 393 return t[i]; 394 if (l <= lo && hi <= r) 395 { 396 t[i] += val; 397 if (lo != hi) 398 { 399 lazy[i * 2] += val; 400 lazy[i * 2 + 1] += val; 401 } 402 return t[i]; 403 } 404 int mid = (lo + hi) / 2; 405 return t[i] = max(update(i * 2, lo, mid, l, r, val), update(i * 2 + 1, mid + 1, hi, l, r, val)); 406 } 407 408 int main() 409 { 410 ios::sync_with_stdio(false); 411 cin.tie(0); 412 int i, j; 413 414 int n, m, k; 415 cin >> n >> m >> k; 416 for (i = 1; i <= n; i++) 417 { 418 for (j = 1; j <= m; j++) 419 { 420 cin >> animal[i][j]; 421 psum[i][j] = psum[i][j - 1] + animal[i][j]; 422 } 423 } 424 425 int mm = m - k + 1; 426 427 for (i = 1; i <= mm; i++) 428 dp[1][i] = psum[1][i + k - 1] - psum[1][i - 1] + psum[2][i + k - 1] - psum[2][i - 1]; 429 for (i = 2; i <= n; i++) 430 { 431 memset(t, 0, sizeof t); 432 memset(lazy, 0, sizeof lazy); 433 for (j = 1; j <= mm; j++) 434 update(1, 1, mm, j, j, dp[i - 1][j]); 435 for (j = 1; j <= k; j++) 436 update(1, 1, mm, 1, j, -animal[i][j]); 437 for (j = 1; j <= mm; j++) 438 { 439 dp[i][j] = t[1] + psum[i][j + k - 1] - psum[i][j - 1] + psum[i + 1][j + k - 1] - psum[i + 1][j - 1]; 440 if (j != mm) 441 { 442 update(1, 1, mm, max(1, j - k + 1), j, animal[i][j]); 443 update(1, 1, mm, j + 1, j + k, -animal[i][j + k]); 444 } 445 } 446 } 447 448 cout << *max_element(dp[n] + 1, dp[n] + mm + 1) << endl; 449 } 450 ``` 451 452 **Solution: O(nm)** 453 454 ``` 455 #include <bits/stdc++.h> 456 using namespace std; 457 using pii = pair<int, int>; 458 using vi = vector<int>; 459 using vvi = vector<vi>; 460 461 const int MAX_N = 50; 462 const int MAX_M = 20000; 463 const int MAX_K = 20; 464 465 int n, m, k; 466 467 inline int ps(vvi &p, int i, int s, int e) 468 { 469 if (s < 1) 470 return p[i][e]; 471 return p[i][e] - p[i][s - 1]; 472 } 473 474 void calc_overlapped(vvi &ar, vvi &p, vvi &dp, int i) 475 { 476 int j; 477 deque<pii> dq; 478 for (j = 1; j <= m - k + 1; j++) 479 { 480 int num = dp[i - 1][j] - ps(p, i, j, j + k - 1); 481 if (dq.size() && dq.front().second <= j - k) 482 dq.pop_front(); 483 while (dq.size() && dq.back().first + ps(p, i, dq.back().second, j - 1) <= num) 484 dq.pop_back(); 485 dq.push_back({ num, j }); 486 dp[i][j] = dq.front().first + ps(p, i, dq.front().second, j - 1) + ps(p, i, j, j + k - 1) + ps(p, i + 1, j, j + k - 1); 487 } 488 } 489 490 int main() 491 { 492 ios::sync_with_stdio(false); 493 cin.tie(0); 494 int i, j; 495 496 cin >> n >> m >> k; 497 498 vvi init(n + 5, vi(m + 5, 0)); 499 vvi animal, animal_rev, psum, psum_rev, lmax, rmax, dp, dpl, dpr; 500 animal = animal_rev = psum = psum_rev = lmax = rmax = dp = dpl = dpr = init; 501 502 for (i = 1; i <= n; i++) 503 { 504 for (j = 1; j <= m; j++) 505 { 506 cin >> animal[i][j]; 507 psum[i][j] = psum[i][j - 1] + animal[i][j]; 508 animal_rev[i][m - j + 1] = animal[i][j]; 509 } 510 for (j = 1; j <= m; j++) 511 psum_rev[i][j] = psum_rev[i][j - 1] + animal_rev[i][j]; 512 } 513 514 deque<pii> dq; 515 for (i = 1; i <= n; i++) 516 { 517 for (j = 1; j <= m - k + 1; j++) 518 { 519 if (j > k) 520 dp[i][j] = lmax[i - 1][j - k]; 521 if (j <= m - k * 2 + 1) 522 dp[i][j] = max(dp[i][j], rmax[i - 1][j + k]); 523 dp[i][j] += ps(psum, i, j, j + k - 1) + ps(psum, i + 1, j, j + k - 1); 524 } 525 526 calc_overlapped(animal, psum, dpl, i); 527 calc_overlapped(animal_rev, psum_rev, dpr, i); 528 529 for (j = 1; j <= m - k + 1; j++) 530 { 531 dp[i][j] = max({ dp[i][j], dpl[i][j], dpr[i][m - j - k + 2] }); 532 dpl[i][j] = dpr[i][m - j - k + 2] = dp[i][j]; 533 } 534 535 for (j = 1; j <= m - k + 1; j++) 536 lmax[i][j] = max(lmax[i][j - 1], dp[i][j]); 537 for (j = m - k + 1; j >= 1; j--) 538 rmax[i][j] = max(rmax[i][j + 1], dp[i][j]); 539 } 540 541 cout << *max_element(dp[n].begin(), dp[n].end()) << endl; 542 } 543 ```