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