1901.md (7254B)
1 Source: https://codeforces.com/blog/entry/122645 2 3 [1901A - Line Trip](/contest/1901/problem/A "Educational Codeforces Round 158 (Rated for Div. 2)") 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 ios::sync_with_stdio(false); cin.tie(0); 20 int t; 21 cin >> t; 22 while (t--) { 23 int n, x; 24 cin >> n >> x; 25 int prev = 0, ans = 0; 26 for (int i = 0; i < n; ++i) { 27 int a; cin >> a; 28 ans = max(ans, a - prev); 29 prev = a; 30 } 31 ans = max(ans, 2 * (x - prev)); 32 cout << ans << '\n'; 33 } 34 } 35 ``` 36 37 [1901B - Chip and Ribbon](/contest/1901/problem/B "Educational Codeforces Round 158 (Rated for Div. 2)") 38 39 Idea: [Roms](/profile/Roms "Master Roms") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution (Roms)** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 const int N = 200'000; 53 54 int t; 55 56 int main() { 57 cin >> t; 58 for (int tc = 0; tc < t; ++tc) { 59 int n; 60 cin >> n; 61 vector <int> cnt(n); 62 long long res = 0; 63 int cur = 0; 64 for (int i = 0; i < n; ++i) { 65 cin >> cnt[i]; 66 if (cnt[i] > cur) 67 res += cnt[i] - cur; 68 cur = cnt[i]; 69 } 70 71 cout << res - 1 << endl; 72 } 73 return 0; 74 } 75 ``` 76 77 [1901C - Add, Divide and Floor](/contest/1901/problem/C "Educational Codeforces Round 158 (Rated for Div. 2)") 78 79 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 80 81 **Tutorial** 82 83 Tutorial is loading... 84 85 **Solution (awoo)** 86 87 ``` 88 for _ in range(int(input())): 89 n = int(input()) 90 a = list(map(int, input().split())) 91 x, y = min(a), max(a) 92 res = [] 93 while x != y: 94 res.append(x % 2) 95 x = (x + res[-1]) // 2 96 y = (y + res[-1]) // 2 97 print(len(res)) 98 if len(res) <= n: 99 print(*res) 100 ``` 101 102 [1901D - Yet Another Monster Fight](/contest/1901/problem/D "Educational Codeforces Round 158 (Rated for Div. 2)") 103 104 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 105 106 **Tutorial** 107 108 Tutorial is loading... 109 110 **Solution (vovuh)** 111 112 ``` 113 #include <bits/stdc++.h> 114 115 using namespace std; 116 117 int main() { 118 #ifdef _DEBUG 119 freopen("input.txt", "r", stdin); 120 // freopen("output.txt", "w", stdout); 121 #endif 122 123 int n; 124 cin >> n; 125 vector<int> a(n); 126 for (auto &it : a) cin >> it; 127 128 vector<int> pref(n), suf(n); 129 for (int i = 0; i < n; ++i) { 130 pref[i] = a[i] + (n - i - 1); 131 suf[i] = a[i] + i; 132 } 133 for (int i = 1; i < n; ++i) { 134 pref[i] = max(pref[i], pref[i - 1]); 135 } 136 for (int i = n - 2; i >= 0; --i) { 137 suf[i] = max(suf[i], suf[i + 1]); 138 } 139 140 int ans = 2e9; 141 for (int i = 0; i < n; ++i) { 142 int cur = a[i]; 143 if (i > 0) cur = max(cur, pref[i - 1]); 144 if (i + 1 < n) cur = max(cur, suf[i + 1]); 145 ans = min(ans, cur); 146 } 147 148 cout << ans << endl; 149 150 return 0; 151 } 152 ``` 153 154 [1901E - Compressed Tree](/contest/1901/problem/E "Educational Codeforces Round 158 (Rated for Div. 2)") 155 156 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 157 158 **Tutorial** 159 160 Tutorial is loading... 161 162 **Solution (Neon)** 163 164 ``` 165 #include <bits/stdc++.h> 166 167 using namespace std; 168 169 using li = long long; 170 171 const li INF = 1e18; 172 const int N = 555555; 173 174 int n; 175 int a[N]; 176 vector<int> g[N]; 177 li dp[N]; 178 li ans; 179 180 void calc(int v, int p) { 181 vector<li> sum(4, -INF); 182 sum[0] = 0; 183 for (int u : g[v]) if (u != p) { 184 calc(u, v); 185 for (int i = 3; i >= 0; --i) { 186 sum[min(i + 1, 3)] = max(sum[min(i + 1, 3)], sum[i] + dp[u]); 187 } 188 } 189 dp[v] = -INF; 190 for (int j = 0; j < 4; ++j) { 191 dp[v] = max(dp[v], sum[j] + (j == 1 ? 0 : a[v])); 192 ans = max(ans, sum[j] + (j == 2 ? 0 : a[v])); 193 } 194 } 195 196 int main() { 197 ios::sync_with_stdio(false); cin.tie(0); 198 int t; 199 cin >> t; 200 while (t--) { 201 cin >> n; 202 for (int i = 0; i < n; ++i) cin >> a[i]; 203 for (int i = 0; i < n; ++i) g[i].clear(); 204 for (int i = 0; i < n - 1; ++i) { 205 int x, y; 206 cin >> x >> y; 207 --x; --y; 208 g[x].push_back(y); 209 g[y].push_back(x); 210 } 211 ans = 0; 212 calc(0, -1); 213 cout << ans << '\n'; 214 } 215 } 216 ``` 217 218 [1901F - Landscaping](/contest/1901/problem/F "Educational Codeforces Round 158 (Rated for Div. 2)") 219 220 Idea: [adedalic](/profile/adedalic "International Master adedalic") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution (adedalic)** 227 228 ``` 229 #include<bits/stdc++.h> 230 231 using namespace std; 232 233 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 234 #define sz(a) int((a).size()) 235 #define all(a) (a).begin(), (a).end() 236 237 #define x first 238 #define y second 239 240 typedef long long li; 241 typedef long double ld; 242 typedef pair<int, int> pt; 243 244 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 245 return out << "(" << p.x << ", " << p.y << ")"; 246 } 247 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 248 fore(i, 0, sz(v)) { 249 if(i) out << " "; 250 out << v[i]; 251 } 252 return out; 253 } 254 255 pt operator+ (const pt &a, const pt &b) { 256 return {a.x + b.x, a.y + b.y}; 257 } 258 pt operator- (const pt &a, const pt &b) { 259 return {a.x - b.x, a.y - b.y}; 260 } 261 li operator *(const pt &a, const pt &b) { 262 return a.x * 1ll * b.x + a.y * 1ll * b.y; 263 } 264 li operator %(const pt &a, const pt &b) { 265 return a.x * 1ll * b.y - a.y * 1ll * b.x; 266 } 267 268 const int INF = int(1e9); 269 const li INF64 = li(1e18); 270 const ld EPS = 1e-9; 271 272 int n; 273 vector<pt> old, nw; 274 275 inline bool read() { 276 if(!(cin >> n)) 277 return false; 278 old.resize(n); 279 nw.resize(n); 280 fore (i, 0, n) { 281 old[i].x = i; 282 cin >> old[i].y; 283 } 284 fore (i, 0, n) { 285 nw[i].x = i; 286 cin >> nw[i].y; 287 } 288 return true; 289 } 290 291 inline ld getTr(const pt &a, const pt &b) { 292 pt tmp = b - a; 293 pt v = {-tmp.y, tmp.x}; 294 ld c = v * a; 295 ld y0 = (c - v.x * 0) / v.y; 296 ld y1 = (c - v.x * li(n - 1)) / v.y; 297 return (y0 + y1); 298 } 299 300 vector<pt> hull(const vector<pt> &ps, int l, int r) { 301 vector<pt> h; 302 fore (i, l, r) { 303 while (sz(h) > 1 && (h[sz(h) - 1] - h[sz(h) - 2]) % (ps[i] - h[sz(h) - 1]) >= 0) 304 h.pop_back(); 305 h.push_back(ps[i]); 306 } 307 return h; 308 } 309 310 inline void solve() { 311 vector<ld> maxTr(n - 1, 0); 312 fore (t, 0, 2) { 313 auto h = hull(old, n / 2, n); 314 315 auto best = [&](const pt &p) { 316 int l = -1, r = sz(h) - 1; 317 while (r - l > 1) { 318 int mid = (l + r) >> 1; 319 if ((h[mid] - p) % (h[mid + 1] - h[mid]) >= 0) 320 l = mid; 321 else 322 r = mid; 323 } 324 return h[r].x; 325 }; 326 327 vector<ld> bs(n / 2 + 1, 0); 328 for (int i = n / 2 - 1; i >= 0; i--) { 329 int j = best(old[i]); 330 bs[i] = getTr(old[i], old[j]); 331 bs[i] = max(bs[i], bs[i + 1]); 332 } 333 334 ld lans = 0; 335 fore (i, 0, n / 2) { 336 int j = best(nw[i]); 337 lans = max(lans, getTr(nw[i], old[j])); 338 maxTr[i] = max({maxTr[i], lans, bs[i + 1]}); 339 } 340 341 reverse(all(old)); 342 reverse(all(nw)); 343 swap(old, nw); 344 fore (i, 0, n) 345 old[i].x = nw[i].x = i; 346 347 reverse(all(maxTr)); 348 } 349 350 maxTr.push_back(maxTr.back()); 351 cout << maxTr << endl; 352 } 353 354 int main() { 355 #ifdef _DEBUG 356 freopen("input.txt", "r", stdin); 357 int tt = clock(); 358 #endif 359 ios_base::sync_with_stdio(false); 360 cin.tie(0), cout.tie(0); 361 cout << fixed << setprecision(12); 362 363 if(read()) { 364 solve(); 365 366 #ifdef _DEBUG 367 cerr << "TIME = " << clock() - tt << endl; 368 tt = clock(); 369 #endif 370 } 371 return 0; 372 } 373 ```