codeforces-scrape

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

1399.md (7929B)


      1 Source: https://codeforces.com/blog/entry/81082
      2 
      3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov").
      4 
      5 [1399A - Удалить наименьшее](/contest/1399/problem/A "Codeforces Round 661 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int t;
     25 	cin >> t;
     26 	while (t--) {
     27 		int n;
     28 		cin >> n;
     29 		vector<int> a(n);
     30 		for (auto &it : a) cin >> it;
     31 		sort(a.begin(), a.end());
     32 		bool ok = true;
     33 		for (int i = 1; i < n; ++i) {
     34 			ok &= (a[i] - a[i - 1] <= 1);
     35 		}
     36 		if (ok) cout << "YES" << endl;
     37 		else cout << "NO" << endl;
     38 	}
     39 	
     40 	return 0;
     41 }
     42 ```
     43 
     44 [1399B - Уравнивание подарков](/contest/1399/problem/B "Codeforces Round 661 (Div. 3)")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54 
     55 using namespace std;
     56 
     57 int main() {
     58 #ifdef _DEBUG
     59 	freopen("input.txt", "r", stdin);
     60 //	freopen("output.txt", "w", stdout);
     61 #endif
     62 	
     63 	int t;
     64 	cin >> t;
     65 	while (t--) {
     66 		int n;
     67 		cin >> n;
     68 		vector<int> a(n), b(n);
     69 		for (auto &it : a) cin >> it;
     70 		for (auto &it : b) cin >> it;
     71 		int mna = *min_element(a.begin(), a.end());
     72 		int mnb = *min_element(b.begin(), b.end());
     73 		long long ans = 0;
     74 		for (int i = 0; i < n; ++i) {
     75 			ans += max(a[i] - mna, b[i] - mnb);
     76 		}
     77 		cout << ans << endl;
     78 	}
     79 	
     80 	return 0;
     81 }
     82 ```
     83 
     84 [1399C - Лодочное соревнование](/contest/1399/problem/C "Codeforces Round 661 (Div. 3)")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 
     95 using namespace std;
     96 
     97 int main() {
     98 #ifdef _DEBUG
     99 	freopen("input.txt", "r", stdin);
    100 //	freopen("output.txt", "w", stdout);
    101 #endif
    102 	
    103 	int t;
    104 	cin >> t;
    105 	while (t--) {
    106 		int n;
    107 		cin >> n;
    108 		vector<int> cnt(n + 1);
    109 		for (int i = 0; i < n; ++i) {
    110 			int x;
    111 			cin >> x;
    112 			++cnt[x];
    113 		}
    114 		int ans = 0;
    115 		for (int s = 2; s <= 2 * n; ++s) {
    116 			int cur = 0;
    117 			for (int i = 1; i < (s + 1) / 2; ++i) {
    118 				if (s - i > n) continue;
    119 				cur += min(cnt[i], cnt[s - i]);
    120 			}
    121 			if (s % 2 == 0) cur += cnt[s / 2] / 2;
    122 			ans = max(ans, cur);
    123 		}
    124 		cout << ans << endl;
    125 	}
    126 	
    127 	return 0;
    128 }
    129 ```
    130 
    131 [1399D - Из бинарной строки в подпоследовательности](/contest/1399/problem/D "Codeforces Round 661 (Div. 3)")
    132 
    133 **Tutorial**
    134 
    135 Tutorial is loading...
    136 
    137 **Solution**
    138 
    139 ```
    140 #include <bits/stdc++.h>
    141 
    142 using namespace std;
    143 
    144 int main() {
    145 #ifdef _DEBUG
    146 	freopen("input.txt", "r", stdin);
    147 //	freopen("output.txt", "w", stdout);
    148 #endif
    149 	
    150 	int t;
    151 	cin >> t;
    152 	while (t--) {
    153 		int n;
    154 		string s;
    155 		cin >> n >> s;
    156 		vector<int> ans(n);
    157 		vector<int> pos0, pos1;
    158 		for (int i = 0; i < n; ++i) {
    159 			int newpos = pos0.size() + pos1.size();
    160 			if (s[i] == '0') {
    161 				if (pos1.empty()) {
    162 					pos0.push_back(newpos);
    163 				} else {
    164 					newpos = pos1.back();
    165 					pos1.pop_back();
    166 					pos0.push_back(newpos);
    167 				}
    168 			} else {
    169 				if (pos0.empty()) {
    170 					pos1.push_back(newpos);
    171 				} else {
    172 					newpos = pos0.back();
    173 					pos0.pop_back();
    174 					pos1.push_back(newpos);
    175 				}
    176 			}
    177 			ans[i] = newpos;
    178 		}
    179 		cout << pos0.size() + pos1.size() << endl;
    180 		for (auto it : ans) cout << it + 1 << " ";
    181 		cout << endl;
    182 	}
    183 	
    184 	return 0;
    185 }
    186 ```
    187 
    188 [1399E1 - Деление весов (простая версия)](/contest/1399/problem/E1 "Codeforces Round 661 (Div. 3)")
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Solution**
    195 
    196 ```
    197 #include <bits/stdc++.h>
    198 
    199 using namespace std;
    200 
    201 vector<int> w, cnt;
    202 vector<vector<pair<int, int>>> g;
    203 
    204 long long getdiff(int i) {
    205 	return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
    206 }
    207 
    208 void dfs(int v, int p = -1) {
    209 	if (g[v].size() == 1) cnt[p] = 1;
    210 	for (auto [to, id] : g[v]) {
    211 		if (id == p) continue;
    212 		dfs(to, id);
    213 		if (p != -1) cnt[p] += cnt[id];
    214 	}
    215 }
    216 
    217 int main() {
    218 #ifdef _DEBUG
    219 	freopen("input.txt", "r", stdin);
    220 //	freopen("output.txt", "w", stdout);
    221 #endif
    222 	
    223 	int t;
    224 	cin >> t;
    225 	while (t--) {
    226 		int n;
    227 		long long s;
    228 		cin >> n >> s;
    229 		w = cnt = vector<int>(n - 1);
    230 		g = vector<vector<pair<int, int>>>(n);
    231 		for (int i = 0; i < n - 1; ++i) {
    232 			int x, y;
    233 			cin >> x >> y >> w[i];
    234 			--x, --y;
    235 			g[x].push_back({y, i});
    236 			g[y].push_back({x, i});
    237 		}
    238 		dfs(0);
    239 		set<pair<long long, int>> st;
    240 		long long cur = 0;
    241 		for (int i = 0; i < n - 1; ++i) {
    242 			st.insert({getdiff(i), i});
    243 			cur += w[i] * 1ll * cnt[i];
    244 		}
    245 		cerr << cur << endl;
    246 		int ans = 0;
    247 		while (cur > s) {
    248 			int id = st.rbegin()->second;
    249 			st.erase(prev(st.end()));
    250 			cur -= getdiff(id);
    251 			w[id] /= 2;
    252 			st.insert({getdiff(id), id});
    253 			++ans;
    254 		}
    255 		cout << ans << endl;
    256 	}
    257 	
    258 	return 0;
    259 }
    260 ```
    261 
    262 [1399E2 - Деление весов (сложная версия)](/contest/1399/problem/E2 "Codeforces Round 661 (Div. 3)")
    263 
    264 **Tutorial**
    265 
    266 Tutorial is loading...
    267 
    268 **Solution**
    269 
    270 ```
    271 #include <bits/stdc++.h>
    272 
    273 using namespace std;
    274 
    275 const int INF = 1e9;
    276 
    277 int n;
    278 vector<int> w, c, cnt;
    279 vector<vector<pair<int, int>>> g;
    280 
    281 long long getdiff(int i) {
    282 	return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
    283 }
    284 
    285 void dfs(int v, int p = -1) {
    286 	if (g[v].size() == 1) cnt[p] = 1;
    287 	for (auto [to, id] : g[v]) {
    288 		if (id == p) continue;
    289 		dfs(to, id);
    290 		if (p != -1) cnt[p] += cnt[id];
    291 	}
    292 }
    293 
    294 vector<long long> get(int clr) {
    295 	set<pair<long long, int>> st;
    296 	long long cur = 0;
    297 	for (int i = 0; i < n - 1; ++i) {
    298 		if (c[i] == clr) {
    299 			st.insert({getdiff(i), i});
    300 			cur += w[i] * 1ll * cnt[i];
    301 		}
    302 	}
    303 	vector<long long> res;
    304 	res.push_back(cur);
    305 	while (cur > 0 && !st.empty()) {
    306 		int id = st.rbegin()->second;
    307 		st.erase(prev(st.end()));
    308 		cur -= getdiff(id);
    309 		res.push_back(cur);
    310 		w[id] /= 2;
    311 		st.insert({getdiff(id), id});
    312 	}
    313 	return res;
    314 }
    315 
    316 int main() {
    317 #ifdef _DEBUG
    318 	freopen("input.txt", "r", stdin);
    319 //	freopen("output.txt", "w", stdout);
    320 #endif
    321 	
    322 	int t;
    323 	cin >> t;
    324 	while (t--) {
    325 		long long s;
    326 		cin >> n >> s;
    327 		w = c = cnt = vector<int>(n - 1);
    328 		g = vector<vector<pair<int, int>>>(n);
    329 		for (int i = 0; i < n - 1; ++i) {
    330 			int x, y;
    331 			cin >> x >> y >> w[i] >> c[i];
    332 			--x, --y;
    333 			g[x].push_back({y, i});
    334 			g[y].push_back({x, i});
    335 		}
    336 		dfs(0);
    337 		vector<long long> v1 = get(1), v2 = get(2);
    338 		int pos = int(v2.size()) - 1;
    339 		int ans = INF;
    340 		for (int i = 0; i < int(v1.size()); ++i) {
    341 			while (pos > 0 && v1[i] + v2[pos - 1] <= s) --pos;
    342 			if (v1[i] + v2[pos] <= s) {
    343 				ans = min(ans, i + pos * 2);
    344 			}
    345 		}
    346 		cout << ans << endl;
    347 	}
    348 	
    349 	return 0;
    350 }
    351 ```
    352 
    353 [1399F - Очередное подмножество отрезков](/contest/1399/problem/F "Codeforces Round 661 (Div. 3)")
    354 
    355 **Tutorial**
    356 
    357 Tutorial is loading...
    358 
    359 **Solution**
    360 
    361 ```
    362 #include <bits/stdc++.h>
    363 
    364 using namespace std;
    365 
    366 vector<vector<int>> rg;
    367 vector<vector<int>> dp;
    368 
    369 int calc(int l, int r) {
    370 	if (dp[l][r] != -1) return dp[l][r];
    371 	dp[l][r] = 0;
    372 	if (l > r) return dp[l][r];
    373 	bool add = count(rg[l].begin(), rg[l].end(), r); // can't be greater than 1
    374 	dp[l][r] = max(dp[l][r], add + (l + 1 > r ? 0 : calc(l + 1, r)));
    375 	for (auto nr : rg[l]) {
    376 		if (nr >= r) continue;
    377 		dp[l][r] = max(dp[l][r], add + calc(l, nr) + (nr + 1 > r ? 0 : calc(nr + 1, r)));
    378 	}
    379 	return dp[l][r];
    380 }
    381 
    382 int main() {
    383 #ifdef _DEBUG
    384 	freopen("input.txt", "r", stdin);
    385 //	freopen("output.txt", "w", stdout);
    386 #endif
    387 	
    388 	int t;
    389 	cin >> t;
    390 	while (t--) {
    391 		int n;
    392 		cin >> n;
    393 		vector<int> l(n), r(n);
    394 		vector<int> val;
    395 		for (int i = 0; i < n; ++i) {
    396 			cin >> l[i] >> r[i];
    397 			val.push_back(l[i]);
    398 			val.push_back(r[i]);
    399 		}
    400 		sort(val.begin(), val.end());
    401 		val.resize(unique(val.begin(), val.end()) - val.begin());
    402 		for (int i = 0; i < n; ++i) {
    403 			l[i] = lower_bound(val.begin(), val.end(), l[i]) - val.begin();
    404 			r[i] = lower_bound(val.begin(), val.end(), r[i]) - val.begin();
    405 		}
    406 		int siz = val.size();
    407 		dp = vector<vector<int>>(siz, vector<int>(siz, -1));
    408 		rg = vector<vector<int>>(siz);
    409 		for (int i = 0; i < n; ++i) {
    410 			rg[l[i]].push_back(r[i]);
    411 		}
    412 		cout << calc(0, siz - 1) << endl;
    413 	}
    414 	
    415 	return 0;
    416 }
    417 ```