2051.md (6658B)
1 Source: https://codeforces.com/blog/entry/137623 2 3 [2051A - Preparing for the Olympiad](/contest/2051/problem/A "Codeforces Round 995 (Div. 3)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 int n; 23 cin >> n; 24 vector<int> a(n), b(n); 25 for (auto &x : a) cin >> x; 26 for (auto &x : b) cin >> x; 27 int ans = a[n - 1]; 28 for (int i = 0; i < n - 1; ++i) 29 ans += max(0, a[i] - b[i + 1]); 30 cout << ans << '\n'; 31 } 32 } 33 ``` 34 35 [2051B - Journey](/contest/2051/problem/B "Codeforces Round 995 (Div. 3)") 36 37 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (BledDest)** 44 45 ``` 46 t = int(input()) 47 for i in range(t): 48 n, a, b, c = map(int, input().split()) 49 sum = a + b + c 50 d = n // sum * 3 51 if n % sum == 0: 52 print(d) 53 elif n % sum <= a: 54 print(d + 1) 55 elif n % sum <= a + b: 56 print(d + 2) 57 else: 58 print(d + 3) 59 ``` 60 61 [2051C - Preparing for the Exam](/contest/2051/problem/C "Codeforces Round 995 (Div. 3)") 62 63 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 64 65 **Tutorial** 66 67 Tutorial is loading... 68 69 **Solution (BledDest)** 70 71 ``` 72 for _ in range(int(input())): 73 n, m, k = map(int, input().split()) 74 a = list(map(int, input().split())) 75 q = list(map(int, input().split())) 76 used = [False for i in range(n + 1)] 77 for i in q: 78 used[i] = True 79 l = len(q) 80 for i in range(m): 81 if l == n or (l == n-1 and not used[a[i]]): 82 print(1, end='') 83 else: 84 print(0, end='') 85 print() 86 ``` 87 88 [2051D - Counting Pairs](/contest/2051/problem/D "Codeforces Round 995 (Div. 3)") 89 90 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Solution (BledDest)** 97 98 ``` 99 def calcLessThanX(a, x): 100 n = len(a) 101 s = sum(a) 102 j = 0 103 ans = 0 104 105 for i in range(n-1, -1, -1): 106 while j < n and s - a[i] - a[j] >= x: 107 j += 1 108 ans += (n - j) 109 110 for i in range(n): 111 if s - a[i] - a[i] < x: 112 ans -= 1 113 114 return ans // 2 115 116 for _ in range(int(input())): 117 n, x, y = map(int, input().split()) 118 a = list(map(int, input().split())) 119 120 a = sorted(a) 121 print(calcLessThanX(a, y+1) - calcLessThanX(a, x)) 122 ``` 123 124 [2051E - Best Price](/contest/2051/problem/E "Codeforces Round 995 (Div. 3)") 125 126 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 127 128 **Tutorial** 129 130 Tutorial is loading... 131 132 **Solution (Neon)** 133 134 ``` 135 #include <bits/stdc++.h> 136 137 using namespace std; 138 139 int main() { 140 ios::sync_with_stdio(false); cin.tie(0); 141 int t; 142 cin >> t; 143 while (t--) { 144 int n, k; 145 cin >> n >> k; 146 vector<int> a(n), b(n); 147 for (auto &x : a) cin >> x; 148 for (auto &x : b) cin >> x; 149 vector<pair<int, int>> ev; 150 for (int i = 0; i < n; ++i) { 151 ev.emplace_back(a[i], 1); 152 ev.emplace_back(b[i], 2); 153 } 154 sort(ev.begin(), ev.end()); 155 long long ans = 0; 156 int cnt = n, bad = 0; 157 for (int i = 0; i < 2 * n;) { 158 auto [x, y] = ev[i]; 159 if (bad <= k) ans = max(ans, x * 1LL * cnt); 160 while (i < 2 * n && ev[i].first == x) { 161 bad += (ev[i].second == 1); 162 bad -= (ev[i].second == 2); 163 cnt -= (ev[i].second == 2); 164 ++i; 165 } 166 } 167 cout << ans << '\n'; 168 } 169 } 170 ``` 171 172 [2051F - Joker](/contest/2051/problem/F "Codeforces Round 995 (Div. 3)") 173 174 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 175 176 **Tutorial** 177 178 Tutorial is loading... 179 180 **Solution (Neon)** 181 182 ``` 183 #include <bits/stdc++.h> 184 185 using namespace std; 186 187 int main() { 188 int t; 189 cin >> t; 190 while (t--) { 191 int n, m, q; 192 cin >> n >> m >> q; 193 vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}}); 194 while (q--) { 195 int x; 196 cin >> x; 197 bool ins = false; 198 for (auto& [l, r] : segs) { 199 if (x < l) l = max(1, l - 1); 200 else if (x > r) r = min(n, r + 1); 201 else { 202 ins = true; 203 if (l == r) l = n + q, r = -q; 204 } 205 } 206 if (ins) { 207 segs[0] = {1, max(segs[0].second, 1)}; 208 segs[2] = {min(segs[2].first, n), n}; 209 } 210 int lf = 0, rg = -1, ans = 0; 211 for (auto [l, r] : segs) { 212 if (l > r) continue; 213 if (l > rg) { 214 ans += max(0, rg - lf + 1); 215 lf = l; rg = r; 216 } 217 rg = max(rg, r); 218 } 219 ans += max(0, rg - lf + 1); 220 cout << ans << ' '; 221 } 222 cout << '\n'; 223 } 224 } 225 ``` 226 227 [2051G - Snakes](/contest/2051/problem/G "Codeforces Round 995 (Div. 3)") 228 229 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 230 231 **Tutorial** 232 233 Tutorial is loading... 234 235 **Solution (adedalic)** 236 237 ``` 238 #include<bits/stdc++.h> 239 240 using namespace std; 241 242 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 243 #define sz(a) int((a).size()) 244 245 const int INF = int(1e9); 246 247 int n, q; 248 vector<int> id, ch; 249 250 bool read() { 251 if (!(cin >> n >> q)) 252 return false; 253 id.resize(q); 254 ch.resize(q); 255 fore (i, 0, q) { 256 char c; 257 cin >> id[i] >> c; 258 id[i]--; 259 ch[i] = c == '+' ? 1 : -1; 260 } 261 return true; 262 } 263 264 int getDist(int s, int t) { 265 int pSum = 0, cMin = 0; 266 fore (e, 0, q) { 267 if (id[e] == t) 268 pSum += ch[e] < 0; 269 if (id[e] == s) 270 pSum -= ch[e] > 0; 271 cMin = min(cMin, pSum); 272 } 273 return -cMin + 1; 274 } 275 276 inline void solve() { 277 vector<vector<int>> minDist(n, vector<int>(n, INF)); 278 279 fore (i, 0, n) fore (j, 0, n) 280 minDist[i][j] = getDist(i, j); 281 282 vector<int> len(n, 0); 283 fore (e, 0, q) 284 len[id[e]] += ch[e] > 0; 285 286 vector< vector<int> > d(1 << n, vector<int>(n, INF)); 287 fore (i, 0, n) 288 d[1 << i][i] = 1; 289 290 fore (mask, 1, 1 << n) fore (lst, 0, n) { 291 if (d[mask][lst] == INF) 292 continue; 293 fore (nxt, 0, n) { 294 if ((mask >> nxt) & 1) 295 continue; 296 int nmask = mask | (1 << nxt); 297 d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]); 298 } 299 } 300 int ans = INF; 301 fore (lst, 0, n) 302 ans = min(ans, d[(1 << n) - 1][lst] + len[lst]); 303 cout << ans << endl; 304 } 305 306 int main() { 307 #ifdef _DEBUG 308 freopen("input.txt", "r", stdin); 309 int tt = clock(); 310 #endif 311 ios_base::sync_with_stdio(false); 312 313 if(read()) { 314 solve(); 315 316 #ifdef _DEBUG 317 cerr << "TIME = " << clock() - tt << endl; 318 tt = clock(); 319 #endif 320 } 321 return 0; 322 } 323 ```