codeforces-scrape

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

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 ```