codeforces-scrape

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

1353.md (4995B)


      1 Source: https://codeforces.com/blog/entry/77373
      2 
      3 All problems, except the problem D, are mine. The problem D author is [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
      4 
      5 [1353A - Most Unstable Array](/contest/1353/problem/A "Codeforces Round 642 (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, m;
     28 		cin >> n >> m;
     29 		cout << min(2, n - 1) * m << endl;
     30 	}
     31 	
     32 	return 0;
     33 }
     34 ```
     35 
     36 [1353B - Two Arrays And Swaps](/contest/1353/problem/B "Codeforces Round 642 (Div. 3)")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Solution**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50 #ifdef _DEBUG
     51 	freopen("input.txt", "r", stdin);
     52 //	freopen("output.txt", "w", stdout);
     53 #endif
     54 	
     55 	int t;
     56 	cin >> t;
     57 	while (t--) {
     58 		int n, k;
     59 		cin >> n >> k;
     60 		vector<int> a(n);
     61 		for (auto &it : a) cin >> it;
     62 		vector<int> b(n);
     63 		for (auto &it : b) cin >> it;
     64 		sort(a.begin(), a.end());
     65 		sort(b.rbegin(), b.rend());
     66 		int ans = 0;
     67 		for (int i = 0; i < n; ++i) {
     68 			if (i < k) ans += max(a[i], b[i]);
     69 			else ans += a[i];
     70 		}
     71 		cout << ans << endl;
     72 	}
     73 	
     74 	return 0;
     75 }
     76 ```
     77 
     78 [1353C - Board Moves](/contest/1353/problem/C "Codeforces Round 642 (Div. 3)")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution**
     85 
     86 ```
     87 #include <bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 int main() {
     92 #ifdef _DEBUG
     93 	freopen("input.txt", "r", stdin);
     94 //	freopen("output.txt", "w", stdout);
     95 #endif
     96 	
     97 	int t;
     98 	cin >> t;
     99 	while (t--) {
    100 		int n;
    101 		cin >> n;
    102 		long long ans = 0;
    103 		for (int i = 1; i <= n / 2; ++i) {
    104 			ans += i * 1ll * i;
    105 		}
    106 		cout << ans * 8 << endl;
    107 	}
    108 	
    109 	return 0;
    110 }
    111 ```
    112 
    113 [1353D - Constructing the Array](/contest/1353/problem/D "Codeforces Round 642 (Div. 3)")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 struct cmp {
    127 	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
    128 		int lena = a.second - a.first + 1;
    129 		int lenb = b.second - b.first + 1;
    130 		if (lena == lenb) return a.first < b.first;
    131 		return lena > lenb;
    132 	}
    133 };
    134 
    135 int main() {
    136 #ifdef _DEBUG
    137 	freopen("input.txt", "r", stdin);
    138 //	freopen("output.txt", "w", stdout);
    139 #endif
    140 	
    141 	int t;
    142 	cin >> t;
    143 	while (t--) {
    144 		int n;
    145 		cin >> n;
    146 		set<pair<int, int>, cmp> segs;
    147 		segs.insert({0, n - 1});
    148 		vector<int> a(n);
    149 		for (int i = 1; i <= n; ++i) {
    150 			pair<int, int> cur = *segs.begin();
    151 			segs.erase(segs.begin());
    152 			int id = (cur.first + cur.second) / 2;
    153 			a[id] = i;
    154 			if (cur.first < id) segs.insert({cur.first, id - 1});
    155 			if (id < cur.second) segs.insert({id + 1, cur.second});
    156 		}
    157 		for (auto it : a) cout << it << " ";
    158 		cout << endl;
    159 	}
    160 	
    161 	return 0;
    162 }
    163 ```
    164 
    165 [1353E - K-periodic Garland](/contest/1353/problem/E "Codeforces Round 642 (Div. 3)")
    166 
    167 **Tutorial**
    168 
    169 Tutorial is loading...
    170 
    171 **Solution**
    172 
    173 ```
    174 #include <bits/stdc++.h>
    175 
    176 using namespace std;
    177 
    178 int main() {
    179 #ifdef _DEBUG
    180 	freopen("input.txt", "r", stdin);
    181 //	freopen("output.txt", "w", stdout);
    182 #endif
    183 	
    184 	auto solve = [](const string &s) {
    185 		int n = s.size();
    186 		int all = count(s.begin(), s.end(), '1');
    187 		int ans = all;
    188 		vector<int> res(n);
    189 		int pref = 0;
    190 		for (int i = 0; i < n; ++i) {
    191 			int cur = (s[i] == '1');
    192 			pref += cur;
    193 			res[i] = 1 - cur;
    194 			if (i > 0) res[i] += min(res[i - 1], pref - cur);
    195 			ans = min(ans, res[i] + all - pref);
    196 		}
    197 		return ans;
    198 	};
    199 	
    200 	int t;
    201 	cin >> t;
    202 	while (t--) {
    203 		int n, k;
    204 		string s;
    205 		cin >> n >> k >> s;
    206 		vector<string> val(k);
    207 		int cnt = count(s.begin(), s.end(), '1');
    208 		for (int i = 0; i < n; ++i) {
    209 			val[i % k] += s[i];
    210 		}
    211 		int ans = 1e9;
    212 		for (auto &it : val) ans = min(ans, solve(it) + (cnt - count(it.begin(), it.end(), '1')));
    213 		cout << ans << endl;
    214 	}
    215 	
    216 	return 0;
    217 }
    218 ```
    219 
    220 [1353F - Decreasing Heights](/contest/1353/problem/F "Codeforces Round 642 (Div. 3)")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution**
    227 
    228 ```
    229 #include <bits/stdc++.h>
    230 
    231 using namespace std;
    232 
    233 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    234 
    235 const long long INF64 = 1e18;
    236 
    237 int main() {
    238 #ifdef _DEBUG
    239 	freopen("input.txt", "r", stdin);
    240 //	freopen("output.txt", "w", stdout);
    241 #endif
    242 	
    243 	int t;
    244 	cin >> t;
    245 	while (t--) {
    246 		int n, m;
    247 		cin >> n >> m;
    248 		vector<vector<long long>> a(n, vector<long long>(m));
    249 		forn(i, n) forn(j, m) {
    250 			cin >> a[i][j];
    251 		}
    252 		long long a00 = a[0][0];
    253 		long long ans = INF64;
    254 		forn(x, n) forn(y, m) {
    255 			long long need = a[x][y] - x - y;
    256 			if (need > a00) continue;
    257 			a[0][0] = need;
    258 			vector<vector<long long>> dp(n, vector<long long>(m, INF64));
    259 			dp[0][0] = a00 - need;
    260 			forn(i, n) forn(j, m) {
    261 				long long need = a[0][0] + i + j;
    262 				if (need > a[i][j]) continue;
    263 				if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j] - need);
    264 				if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j] - need);
    265 			}
    266 			ans = min(ans, dp[n - 1][m - 1]);
    267 		}
    268 		cout << ans << endl;
    269 	}
    270 	
    271 	return 0;
    272 }
    273 ```