1077.md (6772B)
1 Source: https://codeforces.com/blog/entry/63274 2 3 [1077A - Frog Jumping](/contest/1077/problem/A "Codeforces Round 521 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int t; 23 cin >> t; 24 for (int i = 0; i < t; ++i) { 25 int a, b, k; 26 cin >> a >> b >> k; 27 cout << (a - b) * 1ll * (k / 2) + a * (k & 1) << endl; 28 } 29 30 return 0; 31 } 32 ``` 33 34 [1077B - Disturbed People](/contest/1077/problem/B "Codeforces Round 521 (Div. 3)") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution** 41 42 ``` 43 #include <bits/stdc++.h> 44 45 using namespace std; 46 47 int main() { 48 #ifdef _DEBUG 49 freopen("input.txt", "r", stdin); 50 // freopen("output.txt", "w", stdout); 51 #endif 52 53 int n; 54 cin >> n; 55 vector<int> a(n); 56 for (int i = 0; i < n; ++i) { 57 cin >> a[i]; 58 } 59 60 int ans = 0; 61 for (int i = 1; i < n - 1; ++i) { 62 if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1) { 63 ++ans; 64 a[i + 1] = 0; 65 } 66 } 67 cout << ans << endl; 68 69 return 0; 70 } 71 ``` 72 73 [1077C - Good Array](/contest/1077/problem/C "Codeforces Round 521 (Div. 3)") 74 75 **Tutorial** 76 77 Tutorial is loading... 78 79 **Solution** 80 81 ``` 82 #include <bits/stdc++.h> 83 84 using namespace std; 85 86 const int MAX = 1e6; 87 88 int main() { 89 #ifdef _DEBUG 90 freopen("input.txt", "r", stdin); 91 // freopen("output.txt", "w", stdout); 92 #endif 93 94 int n; 95 cin >> n; 96 vector<int> a(n); 97 vector<int> cnt(MAX + 1); 98 for (int i = 0; i < n; ++i) { 99 cin >> a[i]; 100 ++cnt[a[i]]; 101 } 102 long long sum = accumulate(a.begin(), a.end(), 0ll); 103 104 vector<int> ans; 105 for (int i = 0; i < n; ++i) { 106 sum -= a[i]; 107 --cnt[a[i]]; 108 if (sum % 2 == 0 && sum / 2 <= MAX && cnt[sum / 2] > 0) { 109 ans.push_back(i); 110 } 111 sum += a[i]; 112 ++cnt[a[i]]; 113 } 114 115 cout << ans.size() << endl; 116 for (auto it : ans) cout << it + 1 << " "; 117 cout << endl; 118 119 return 0; 120 } 121 ``` 122 123 [1077D - Cutting Out](/contest/1077/problem/D "Codeforces Round 521 (Div. 3)") 124 125 **Tutorial** 126 127 Tutorial is loading... 128 129 **Solution** 130 131 ``` 132 #include <bits/stdc++.h> 133 134 using namespace std; 135 136 const int MAX = 200 * 1000 + 1; 137 138 int n, k; 139 vector<int> s, t; 140 vector<int> cnts(MAX); 141 142 bool can(int cnt) { 143 t.clear(); 144 for (int i = 0; i < MAX; ++i) { 145 int need = min(cnts[i] / cnt, k - int(t.size())); 146 for (int j = 0; j < need; ++j) { 147 t.push_back(i); 148 } 149 } 150 return int(t.size()) == k; 151 } 152 153 int main() { 154 #ifdef _DEBUG 155 freopen("input.txt", "r", stdin); 156 // freopen("output.txt", "w", stdout); 157 #endif 158 159 cin >> n >> k; 160 s = vector<int>(n); 161 for (int i = 0; i < n; ++i) { 162 cin >> s[i]; 163 } 164 for (auto c : s) { 165 ++cnts[c]; 166 } 167 168 int l = 0, r = n; 169 while (r - l > 1) { 170 int mid = (l + r) >> 1; 171 if (can(mid)) { 172 l = mid; 173 } else { 174 r = mid; 175 } 176 } 177 if (!can(r)) can(l); 178 for (auto it : t) cout << it << " "; 179 cout << endl; 180 181 return 0; 182 } 183 ``` 184 185 [1077E - Thematic Contests](/contest/1077/problem/E "Codeforces Round 521 (Div. 3)") 186 187 **Tutorial** 188 189 Tutorial is loading... 190 191 **Solution** 192 193 ``` 194 #include <bits/stdc++.h> 195 196 using namespace std; 197 198 int main() { 199 #ifdef _DEBUG 200 freopen("input.txt", "r", stdin); 201 // freopen("output.txt", "w", stdout); 202 #endif 203 204 int n; 205 cin >> n; 206 map<int, int> cnt; 207 for (int i = 0; i < n; ++i) { 208 int x; 209 cin >> x; 210 ++cnt[x]; 211 } 212 213 vector<int> cnts; 214 for (auto it : cnt) { 215 cnts.push_back(it.second); 216 } 217 sort(cnts.begin(), cnts.end()); 218 219 int ans = 0; 220 for (int i = 1; i <= cnts.back(); ++i) { 221 int pos = int(cnts.size()) - 1; 222 int cur = i; 223 int res = cur; 224 while (cur % 2 == 0 && pos > 0) { 225 cur /= 2; 226 --pos; 227 if (cnts[pos] < cur) break; 228 res += cur; 229 } 230 ans = max(ans, res); 231 } 232 cout << ans << endl; 233 234 return 0; 235 } 236 ``` 237 238 [1077F1 - Pictures with Kittens (easy version)](/contest/1077/problem/F1 "Codeforces Round 521 (Div. 3)") 239 240 **Tutorial** 241 242 Tutorial is loading... 243 244 **Solution** 245 246 ``` 247 #include <bits/stdc++.h> 248 249 using namespace std; 250 251 const long long INF64 = 1e18; 252 253 int main() { 254 #ifdef _DEBUG 255 freopen("input.txt", "r", stdin); 256 // freopen("output.txt", "w", stdout); 257 #endif 258 259 int n, k, x; 260 cin >> n >> k >> x; 261 vector<int> a(n); 262 for (int i = 0; i < n; ++i) { 263 cin >> a[i]; 264 } 265 vector<vector<long long>> dp(n + 1, vector<long long>(x + 1, -INF64)); 266 267 dp[0][x] = 0; 268 for (int i = 1; i <= n; ++i) { 269 for (int j = 0; j < x; ++j) { 270 for (int p = 1; p <= k; ++p) { 271 if (i - p < 0) break; 272 if (dp[i - p][j + 1] == -INF64) { 273 continue; 274 } 275 dp[i][j] = max(dp[i][j], dp[i - p][j + 1] + a[i - 1]); 276 } 277 } 278 } 279 280 long long ans = -INF64; 281 for (int i = n - k + 1; i <= n; ++i) { 282 ans = max(ans, *max_element(dp[i].begin(), dp[i].end())); 283 } 284 if (ans == -INF64) ans = -1; 285 cout << ans << endl; 286 287 return 0; 288 } 289 ``` 290 291 [1077F2 - Pictures with Kittens (hard version)](/contest/1077/problem/F2 "Codeforces Round 521 (Div. 3)") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 using namespace std; 303 304 #define x first 305 #define y second 306 #define mp make_pair 307 308 typedef long long li; 309 typedef pair<li, li> pll; 310 311 const li INF64 = 1e18; 312 313 struct myQueue { 314 stack<pll> s1, s2; 315 316 int size() { 317 return s1.size() + s2.size(); 318 } 319 320 bool isEmpty() { 321 return size() == 0; 322 } 323 324 long long getMax() { 325 if (isEmpty()) { 326 return -INF64; 327 } 328 if (!s1.empty() && !s2.empty()) { 329 return max(s1.top().y, s2.top().y); 330 } 331 if (!s1.empty()) { 332 return s1.top().y; 333 } 334 return s2.top().y; 335 } 336 337 void push(long long val) { 338 if (s2.empty()) { 339 s2.push(mp(val, val)); 340 } else { 341 s2.push(mp(val, max(val, s2.top().y))); 342 } 343 } 344 345 void pop() { 346 if (s1.empty()) { 347 while (!s2.empty()) { 348 if (s1.empty()) { 349 s1.push(mp(s2.top().x, s2.top().x)); 350 } else { 351 s1.push(mp(s2.top().x, max(s2.top().x, s1.top().y))); 352 } 353 s2.pop(); 354 } 355 } 356 assert(!s1.empty()); 357 s1.pop(); 358 } 359 }; 360 361 int n, k, x; 362 vector<int> a; 363 364 vector<myQueue> q; 365 vector<queue<int>> pos; 366 vector<vector<long long>> dp; 367 368 int main() { 369 #ifdef _DEBUG 370 freopen("input.txt", "r", stdin); 371 // freopen("output.txt", "w", stdout); 372 #endif 373 374 cin >> n >> k >> x; 375 a = vector<int>(n); 376 for (int i = 0; i < n; ++i) { 377 cin >> a[i]; 378 } 379 q = vector<myQueue>(x + 1); 380 pos = vector<queue<int>>(x + 1); 381 dp = vector<vector<long long>>(n + 1, vector<long long>(x + 1, -INF64)); 382 383 dp[0][x] = 0; 384 pos[x].push(-1); 385 q[x].push(0ll); 386 387 for (int i = 1; i <= n; ++i) { 388 for (int j = 0; j <= x; ++j) { 389 while (!pos[j].empty() && pos[j].front() < i - k - 1) { 390 q[j].pop(); 391 pos[j].pop(); 392 } 393 } 394 for (int j = 0; j < x; ++j) { 395 if (!q[j + 1].isEmpty()) { 396 dp[i][j] = max(dp[i][j], q[j + 1].getMax() + a[i - 1]); 397 q[j].push(dp[i][j]); 398 pos[j].push(i - 1); 399 } 400 } 401 } 402 403 long long ans = -INF64; 404 for (int i = n - k + 1; i <= n; ++i) { 405 ans = max(ans, *max_element(dp[i].begin(), dp[i].end())); 406 } 407 if (ans == -INF64) ans = -1; 408 cout << ans << endl; 409 410 return 0; 411 } 412 ```