708.md (6499B)
1 Source: https://codeforces.com/blog/entry/46763 2 3 Tutorial is loading... 4 5 **Code** 6 7 ``` 8 int main() { 9 int n, b, d; 10 std::cin >> n >> b >> d; 11 12 int current_size = 0; 13 int result = 0; 14 int x; 15 for (; n > 0; --n) { 16 std::cin >> x; 17 if (x > b) { 18 continue; 19 } 20 current_size += x; 21 if (current_size > d) { 22 ++result; 23 current_size = 0; 24 } 25 } 26 27 std::cout << result << "\n"; 28 return 0; 29 } 30 ``` 31 32 Tutorial is loading... 33 34 **Code** 35 36 ``` 37 const int MAXN = 100000; 38 39 int x[MAXN]; 40 41 int main() { 42 int n, A; 43 scanf("%d %d", &n, &A); 44 if (n == 1) { 45 printf("0\n"); 46 return 0; 47 } 48 for (int i = 0; i < n; i++) { 49 scanf("%d", &x[i]); 50 } 51 int first_max = -2e6; 52 int second_max = -2e6; 53 int first_min = 2e6; 54 int second_min = 2e6; 55 56 for (int i = 0; i < n; i++) { 57 if (x[i] > second_max) { 58 second_max = x[i]; 59 if (second_max > first_max) { 60 swap(second_max, first_max); 61 } 62 } 63 if (x[i] < second_min) { 64 second_min = x[i]; 65 if (second_min < first_min) { 66 swap(second_min, first_min); 67 } 68 } 69 } 70 printf("%d\n", min(first_max - second_min + min(abs(A - first_max), abs(A - second_min)), 71 second_max - first_min + min(abs(A - second_max), abs(A - first_min)))); 72 73 return 0; 74 } 75 ``` 76 77 Tutorial is loading... 78 79 **Code** 80 81 ``` 82 void solve() { 83 string s; 84 cin >> s; 85 for (int i = 0; i < s.length(); ++i) { 86 if (s[i] == 'a') { 87 continue; 88 } 89 int j = i + 1; 90 while (j < s.length() && s[j] != 'a') { 91 ++j; 92 } 93 for (int r = i; r < j; ++r) { 94 --s[r]; 95 } 96 cout << s << "\n"; 97 return; 98 } 99 100 s.back() = 'z'; 101 cout << s << "\n"; 102 103 } 104 ``` 105 106 Tutorial is loading... 107 108 **Code** 109 110 ``` 111 void imp() { 112 cout << "Impossible\n"; 113 exit(0); 114 } 115 116 ll invtriange(ll x) { 117 ll l = 1, r = 1000000; 118 while (r - l > 1) { 119 ll m = (l + r) / 2; 120 if (m * (m - 1) / 2 > x) r = m; 121 else l = m; 122 } 123 if (l * (l - 1) / 2 != x) { 124 imp(); 125 } 126 return l; 127 } 128 129 int main() { 130 vvl a(2, vl(2)); 131 for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) { 132 cin >> a[i][j]; 133 } 134 if (a[0][0] + a[0][1] + a[1][0] + a[1][1] == 0) { 135 cout << "0\n"; 136 return 0; 137 } 138 ll c0 = invtriange(a[0][0]); 139 ll c1 = invtriange(a[1][1]); 140 if (a[0][0] == 0 || a[1][1] == 0) { 141 if (a[0][1] + a[1][0] == 0) { 142 if (c0 == 1) c0 = 0; 143 if (c1 == 1) c1 = 0; 144 cout << string(c0, '0') << string(c1, '1'); 145 return 0; 146 } 147 } 148 if (c0 * c1 != a[0][1] + a[1][0]) { 149 imp(); 150 } 151 string s(c0 + c1, '0'); 152 for (int i = 0; i < s.size(); ++i) { 153 if (c0 == 0 || a[0][1] < c1) { 154 s[i] = '1'; 155 a[1][0] -= c0; 156 --c1; 157 } else { 158 a[0][1] -= c1; 159 --c0; 160 } 161 } 162 cout << s << endl; 163 return 0; 164 } 165 ``` 166 167 Tutorial is loading... 168 169 **Code** 170 171 ``` 172 int n; 173 vector<vector<int>> g; 174 vector<int> cnt; 175 176 int min_mx = 1e9; 177 int center = -1; 178 179 void dfs(int v, int p) { 180 cnt[v] = 1; 181 int mx = 0; 182 for (int to : g[v]) { 183 if (to == p) { 184 continue; 185 } 186 dfs(to, v); 187 cnt[v] += cnt[to]; 188 mx = max(mx, cnt[to]); 189 } 190 mx = max(mx, n - cnt[v]); 191 if (mx < min_mx) { 192 min_mx = mx; 193 center = v; 194 } 195 } 196 197 vector<pair<int, int>> subtrees; 198 vector<int> ans; 199 200 void dfs1(int v, int p, int sum_other, int prev) { 201 if (sum_other <= n / 2) { 202 ans[v] = 1; 203 } 204 for (int i = 0; i < 2 && i < subtrees.size(); ++i) { 205 if (subtrees[i].second == prev) { 206 continue; 207 } 208 if (n - cnt[v] - subtrees[i].first <= n / 2) { 209 ans[v] = 1; 210 } 211 } 212 for (int to : g[v]) { 213 if (to == p) { 214 continue; 215 } 216 dfs1(to, v, sum_other, prev); 217 } 218 } 219 220 void solve() { 221 cin >> n; 222 g.resize(n); 223 cnt.assign(n, 0); 224 for (int i = 1; i < n; ++i) { 225 int a, b; 226 cin >> a >> b; 227 --a; --b; 228 g[a].push_back(b); 229 g[b].push_back(a); 230 } 231 dfs(0, 0); 232 233 assert(center != -1); 234 ans.assign(n, 0); 235 ans[center] = 1; 236 dfs(center, center); 237 int sum_all = 0; 238 for (int to : g[center]) { 239 subtrees.emplace_back(cnt[to], to); 240 sum_all += cnt[to]; 241 } 242 sort(all(subtrees)); 243 reverse(all(subtrees)); 244 245 for (int to : g[center]) { 246 dfs1(to, center, n - cnt[to], to); 247 } 248 249 for (int i = 0; i < n; ++i) { 250 cout << ans[i] << ' '; 251 } 252 cout << "\n"; 253 254 } 255 ``` 256 257 Tutorial is loading... 258 259 **Code** 260 261 ``` 262 class FixFlow { 263 public: 264 void solve(std::istream& in, std::ostream& out) { 265 int n, m; 266 in >> n >> m; 267 int s = n; 268 int t = n + 1; 269 MinCostFlow<int, int> flow(n + 2); 270 vector<int> balance(n); 271 int INF = 1000000000; 272 flow.addEdge((size_t) (n - 1), 0, INF, 0); 273 274 int defaultAnswer = 0; 275 for (int i: range(m)) { 276 int a, b, c, f; 277 in >> a >> b >> c >> f; 278 --a, --b; 279 balance[a] += f; 280 balance[b] -= f; 281 if (f <= c) { 282 flow.addEdge(a, b, c - f, 1); 283 flow.addEdge(a, b, INF, 2); 284 flow.addEdge(b, a, f, 1); 285 } else { 286 // f > c 287 defaultAnswer += f - c; 288 flow.addEdge(a, b, INF, 2); 289 flow.addEdge(b, a, f - c, 0); 290 flow.addEdge(b, a, c, 1); 291 } 292 } 293 294 int sumB = 0; 295 for (int i: range(n)) { 296 if (balance[i] > 0) { 297 flow.addEdge(i, t, balance[i], 0); 298 sumB += balance[i]; 299 } else { 300 flow.addEdge(s, i, -balance[i], 0); 301 } 302 } 303 304 auto res = flow.findFlow(s, t, MinCostMaxFlowStrategy()); 305 assert(res.flow == sumB); 306 out << res.cost + defaultAnswer << "\n"; 307 } 308 }; 309 ``` 310 311 Tutorial is loading... 312 313 **Code** 314 315 ``` 316 class MAI { 317 public: 318 void solve(std::istream& in, std::ostream& out) { 319 int N, m; 320 int a, b; 321 int k; 322 in >> N >> m >> a >> b >> k; 323 using Z = ZnConst<1000000007>; 324 Z p = Z::valueOf(a) / b; 325 Z q = 1 - p; 326 327 // dp[r'] = sum l < r <= r' d[l][r] 328 vector<Z> dp(m + 1, Z()); 329 dp[m] = 1; 330 331 vector<Z> powersP(k + 1), powersQ(k + 1); 332 powersP[0] = powersQ[0] = 1; 333 for (int i: range(k)) { 334 powersP[i + 1] = powersP[i] * p; 335 powersQ[i + 1] = powersQ[i] * q; 336 } 337 338 vector<Z> fact = factorials<Z>(k + 1); 339 vector<Z> invfact = fact; 340 for (auto& x: invfact) { 341 x = 1 / x; 342 } 343 344 auto get_p_one_side = [&](int l) { 345 if (l > k) { 346 return Z(); 347 } 348 return powersP[l] * powersQ[k - l] * fact[k] * invfact[l] * invfact[k - l]; 349 }; 350 351 for (int iter: range(N)) { 352 vector<Z> dp_one(m + 1, Z()); 353 Z sumPl, sumPlDpl; 354 355 for (int r: inclusiveRange(m)) { 356 //new_d[l][r] = p[l] * p[n - r] * (have_something - dp[l] - dp[n - r]) 357 Z have_something = dp.back(); 358 dp_one[r] = get_p_one_side(m - r) * ( 359 have_something * sumPl - sumPlDpl - sumPl * dp[m - r] 360 ); 361 sumPl += get_p_one_side(r); 362 sumPlDpl += get_p_one_side(r) * dp[r]; 363 } 364 365 for (int i: range(m)) { 366 dp_one[i + 1] += dp_one[i]; 367 } 368 369 dp = move(dp_one); 370 } 371 372 out << dp.back(); 373 } 374 }; 375 ```