1082.md (8933B)
1 Source: https://codeforces.com/blog/entry/63544 2 3 [1082A - Vasya and Book](/contest/1082/problem/A "Educational Codeforces Round 55 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Ajosteen)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 const int INF = int(2e9) + 99; 17 18 int n, x, y, d; 19 20 int dist(int x, int y){ 21 return (abs(x - y) + (d - 1)) / d; 22 } 23 24 int main() { 25 26 int t; 27 cin >> t; 28 for(int i = 0; i < t; ++i){ 29 cin >> n >> x >> y >> d; 30 31 int len = abs(x - y); 32 int res = INF; 33 34 if(len % d == 0) 35 res = min(res, dist(x, y)); 36 37 len = y - 1; 38 if(len % d == 0) 39 res = min(res, dist(x, 1) + dist(1, y)); 40 41 len = n - y; 42 if(len % d == 0) 43 res = min(res, dist(x, n) + dist(n, y)); 44 45 if(res == INF) 46 res = -1; 47 48 cout << res << endl; 49 } 50 51 return 0; 52 } 53 ``` 54 55 [1082B - Vova and Trophies](/contest/1082/problem/B "Educational Codeforces Round 55 (Rated for Div. 2)") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution (Ajosteen)** 62 63 ``` 64 #include <bits/stdc++.h> 65 66 using namespace std; 67 68 int n; 69 string s; 70 71 int main() { 72 73 cin >> n >> s; 74 75 vector <int> l(n), r(n); 76 for(int i = 0; i < n; ++i){ 77 if(s[i] == 'G'){ 78 l[i] = 1; 79 if(i > 0) l[i] += l[i - 1]; 80 } 81 } 82 for(int i = n - 1; i >= 0; --i){ 83 if(s[i] == 'G'){ 84 r[i] = 1; 85 if(i + 1 < n) r[i] += r[i + 1]; 86 } 87 } 88 89 90 int res = 0; 91 int cntG = 0; 92 for(int i = 0; i < n; ++i) 93 cntG += s[i] == 'G'; 94 95 for(int i = 0; i < n; ++i){ 96 if(s[i] == 'G') continue; 97 int nres = 1; 98 if(i > 0) nres += l[i - 1]; 99 if(i + 1 < n) nres += r[i + 1]; 100 res = max(res, nres); 101 } 102 103 res = min(res, cntG); 104 if(cntG == n) res = cntG; 105 cout << res << endl; 106 return 0; 107 } 108 ``` 109 110 [1082C - Multi-Subject Competition](/contest/1082/problem/C "Educational Codeforces Round 55 (Rated for Div. 2)") 111 112 **Tutorial** 113 114 Tutorial is loading... 115 116 **Solution (adedalic)** 117 118 ``` 119 #include<bits/stdc++.h> 120 using namespace std; 121 122 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 123 #define sz(a) int((a).size()) 124 125 int n, m; 126 vector<int> s, r; 127 128 inline bool read() { 129 if(!(cin >> n >> m)) 130 return false; 131 s.assign(n, 0); 132 r.assign(n, 0); 133 134 fore(i, 0, n) { 135 assert(cin >> s[i] >> r[i]); 136 s[i]--; 137 } 138 return true; 139 } 140 141 vector< vector<int> > subs; 142 143 inline void solve() { 144 subs.assign(m + 1, vector<int>()); 145 146 fore(i, 0, n) 147 subs[s[i]].push_back(r[i]); 148 149 fore(id, 0, sz(subs)) { 150 sort(subs[id].begin(), subs[id].end()); 151 reverse(subs[id].begin(), subs[id].end()); 152 } 153 154 vector<int> mx(n + 5, 0); 155 fore(id, 0, sz(subs)) { 156 int curSum = 0; 157 fore(i, 0, sz(subs[id])) { 158 curSum += subs[id][i]; 159 if(curSum < 0) 160 break; 161 162 mx[i + 1] += curSum; 163 } 164 } 165 166 cout << *max_element(mx.begin(), mx.end()) << endl; 167 } 168 169 int main() { 170 #ifdef _DEBUG 171 freopen("input.txt", "r", stdin); 172 int tt = clock(); 173 #endif 174 cout << fixed << setprecision(15); 175 176 if(read()) { 177 solve(); 178 179 #ifdef _DEBUG 180 cerr << "TIME = " << clock() - tt << endl; 181 tt = clock(); 182 #endif 183 } 184 return 0; 185 } 186 ``` 187 188 [1082D - Maximum Diameter Graph](/contest/1082/problem/D "Educational Codeforces Round 55 (Rated for Div. 2)") 189 190 **Tutorial** 191 192 Tutorial is loading... 193 194 **Solution (PikMike)** 195 196 ``` 197 #include <bits/stdc++.h> 198 199 #define forn(i, n) for (int i = 0; i < int(n); i++) 200 201 using namespace std; 202 203 const int N = 1000 + 7; 204 205 int n; 206 int a[N]; 207 208 int main() { 209 scanf("%d", &n); 210 forn(i, n) 211 scanf("%d", &a[i]); 212 213 int sum = 0; 214 forn(i, n) 215 sum += a[i]; 216 217 if (sum < 2 * n - 2){ 218 puts("NO"); 219 return 0; 220 } 221 222 vector<int> ones; 223 forn(i, n) if (a[i] == 1){ 224 a[i] = 0; 225 ones.push_back(i); 226 } 227 228 int t = ones.size(); 229 int dm = (n - t) - 1 + min(2, t); 230 printf("YES %d\n%d\n", dm, n - 1); 231 232 int lst = -1; 233 if (!ones.empty()){ 234 lst = ones.back(); 235 ones.pop_back(); 236 } 237 238 forn(i, n){ 239 if (a[i] > 1){ 240 if (lst != -1){ 241 --a[lst]; 242 --a[i]; 243 printf("%d %d\n", lst + 1, i + 1); 244 } 245 lst = i; 246 } 247 } 248 249 for (int i = n - 1; i >= 0; --i){ 250 while (!ones.empty() && a[i] > 0){ 251 --a[i]; 252 printf("%d %d\n", i + 1, ones.back() + 1); 253 ones.pop_back(); 254 } 255 } 256 return 0; 257 } 258 ``` 259 260 [1082E - Increasing Frequency](/contest/1082/problem/E "Educational Codeforces Round 55 (Rated for Div. 2)") 261 262 **Tutorial** 263 264 Tutorial is loading... 265 266 **Solution (adedalic)** 267 268 ``` 269 #include<bits/stdc++.h> 270 using namespace std; 271 272 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 273 #define sz(a) int((a).size()) 274 275 const int INF = int(1e9); 276 277 int n, c; 278 vector<int> a; 279 280 inline bool read() { 281 if(!(cin >> n >> c)) 282 return false; 283 a.assign(n, 0); 284 fore(i, 0, n) 285 assert(scanf("%d", &a[i]) == 1); 286 return true; 287 } 288 289 vector<int> cntC; 290 291 int getCnt(int l, int r) { 292 return cntC[r] - cntC[l]; 293 } 294 295 vector< vector<int> > segs; 296 vector<int> lst; 297 298 int maxSegment(const vector<int> &s) { 299 int mx = -INF; 300 301 int bal = 0; 302 fore(i, 0, sz(s)) { 303 bal = max(0, bal + s[i]); 304 mx = max(mx, bal); 305 } 306 return mx; 307 } 308 309 inline void solve() { 310 cntC.assign(n + 1, 0); 311 fore(i, 0, n) 312 cntC[i + 1] = cntC[i] + (a[i] == c); 313 314 int cntDif = *max_element(a.begin(), a.end()) + 1; 315 segs.assign(cntDif, vector<int>()); 316 lst.assign(cntDif, -1); 317 318 fore(i, 0, n) { 319 segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i)); 320 lst[a[i]] = i; 321 segs[a[i]].push_back(1); 322 } 323 fore(v, 0, cntDif) 324 segs[v].push_back(-getCnt(lst[v] + 1, n)); 325 326 int ans = 0; 327 fore(v, 0, cntDif) { 328 if(v == c) continue; 329 ans = max(ans, maxSegment(segs[v])); 330 } 331 332 cout << getCnt(0, n) + ans << endl; 333 } 334 335 int main() { 336 #ifdef _DEBUG 337 freopen("input.txt", "r", stdin); 338 int tt = clock(); 339 #endif 340 cout << fixed << setprecision(15); 341 342 if(read()) { 343 solve(); 344 345 #ifdef _DEBUG 346 cerr << "TIME = " << clock() - tt << endl; 347 tt = clock(); 348 #endif 349 } 350 return 0; 351 } 352 ``` 353 354 [1082F - Speed Dial](/contest/1082/problem/F "Educational Codeforces Round 55 (Rated for Div. 2)") 355 356 **Tutorial** 357 358 Tutorial is loading... 359 360 **Solution (PikMike)** 361 362 ``` 363 #include <bits/stdc++.h> 364 365 #define forn(i, n) for (int i = 0; i < int(n); i++) 366 367 using namespace std; 368 369 const int N = 500 + 7; 370 const int M = 11; 371 const int INF = 1e9; 372 373 struct node{ 374 int nxt[10]; 375 int cnt; 376 node(){ 377 memset(nxt, -1, sizeof(nxt)); 378 cnt = 0; 379 } 380 }; 381 382 node trie[N]; 383 int cnt; 384 int h[N]; 385 386 void add(string s, int m){ 387 int cur = 0; 388 forn(i, s.size()){ 389 int c = s[i] - '0'; 390 if (trie[cur].nxt[c] == -1){ 391 trie[cur].nxt[c] = cnt; 392 h[cnt] = h[cur] + 1; 393 ++cnt; 394 } 395 cur = trie[cur].nxt[c]; 396 } 397 trie[cur].cnt += m; 398 } 399 400 int n, k; 401 402 int dp[N][M][N]; 403 int dp2[N][M][N][M]; 404 405 int calc(int x, int rem, int k){ 406 if (dp[x][rem][k] != -1) 407 return dp[x][rem][k]; 408 409 vector<int> ch; 410 forn(i, 10) if (trie[x].nxt[i] != -1) 411 ch.push_back(trie[x].nxt[i]); 412 413 dp[x][rem][k] = INF; 414 if (rem > 0) 415 dp[x][rem][k] = min(dp[x][rem][k], calc(x, rem - 1, x)); 416 417 dp2[x][rem][k][ch.size()] = 0; 418 for (int i = int(ch.size()) - 1; i >= 0; --i) forn(z, rem + 1) 419 dp2[x][rem][k][i] = min(dp2[x][rem][k][i], calc(ch[i], z, k) + dp2[x][rem - z][k][i + 1]); 420 421 dp[x][rem][k] = min(dp[x][rem][k], dp2[x][rem][k][0] + (h[x] - h[k]) * trie[x].cnt); 422 423 return dp[x][rem][k]; 424 } 425 426 int main() { 427 trie[0] = node(); 428 cnt = 1; 429 430 cin >> n >> k; 431 forn(i, n){ 432 string s; 433 int m; 434 cin >> s >> m; 435 add(s, m); 436 } 437 438 memset(dp, -1, sizeof(dp)); 439 440 forn(i, N) forn(j, M) forn(l, N) forn(t, M) 441 dp2[i][j][l][t] = INF; 442 443 int ans = calc(0, k, 0); 444 445 cout << ans << endl; 446 return 0; 447 } 448 ``` 449 450 [1082G - Petya and Graph](/contest/1082/problem/G "Educational Codeforces Round 55 (Rated for Div. 2)") 451 452 **Tutorial** 453 454 Tutorial is loading... 455 456 **Solution (Ajosteen)** 457 458 ``` 459 #include <bits/stdc++.h> 460 461 using namespace std; 462 463 typedef long long li; 464 465 const int N = 2009; 466 const int INF = int(1e9) + 777; 467 468 struct edge{ 469 int to, f, c; 470 edge () {} 471 edge (int to, int f, int c) : to(to), f(f), c(c) {} 472 }; 473 474 int n, m; 475 int s, t; 476 vector<edge> edges; 477 vector <int> g[N]; 478 int u[N], cu; 479 480 void addEdge(int v, int to, int cap){ 481 482 g[v].push_back(edges.size()); 483 edges.push_back(edge(to, 0, cap)); 484 485 g[to].push_back(edges.size()); 486 edges.push_back(edge(v, 0, 0)); 487 } 488 489 int dfs(int v, int need){ 490 if(v == t) return need; 491 u[v] = cu; 492 for(auto to : g[v]){ 493 edge &e = edges[to]; 494 if(u[e.to] != cu && e.c - e.f >= need){ 495 int add = dfs(e.to, need); 496 if(add > 0){ 497 edges[to].f += add; 498 edges[to ^ 1].f -= add; 499 return add; 500 } 501 } 502 } 503 return 0; 504 } 505 506 li enlarge(int k){ 507 li res = 0; 508 while(true){ 509 ++cu; 510 int add = dfs(s, k); 511 res += add; 512 if(add == 0) break; 513 } 514 return res; 515 } 516 517 li maxFlow(){ 518 li flow = 0; 519 for(int k = (1 << 29); k > 0; k >>= 1){ 520 flow += enlarge(k); 521 } 522 return flow; 523 } 524 525 int main() { 526 //freopen("input.txt", "r", stdin); 527 int nn, mm; 528 cin >> nn >> mm; 529 n = nn + mm + 5; 530 m = nn + mm + mm + mm + 5; 531 s = n - 1, t = n - 2; 532 533 for(int i = 0; i < nn; ++i){ 534 int a; 535 cin >> a; 536 addEdge(i + mm, t, a); 537 } 538 539 li sum = 0; 540 for(int i = 0; i < mm; ++i){ 541 int u, v, w; 542 cin >> u >> v >> w; 543 --u, --v; 544 sum += w; 545 546 addEdge(s, i, w); 547 addEdge(i, u + mm, INF); 548 addEdge(i, v + mm, INF); 549 } 550 551 li fl = maxFlow(); 552 cout << sum - fl << endl; 553 554 return 0; 555 } 556 ```