smatskevich

Raspisanie

Nov 27th, 2021
639
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. typedef long long ll;
  5.  
  6. int main() {
  7.   ll n = 0;
  8.   ll limit = 0;
  9.   std::cin >> n >> limit;
  10.   std::vector<ll> l(n);
  11.   for (int i = 0; i < n; ++i) std::cin >> l[i];
  12.   std::vector<ll> c(n);
  13.   for (int i = 0; i < n; ++i) std::cin >> c[i];
  14.  
  15.   ll b = 0, e = 0; // Окно от кружка b до кружка e.
  16.   ll part_b = 0; // Количество минут от старта кружка b[b] в окне.
  17.   ll part_e = 0; // Количество минут от старта кружка l[e] в окне.
  18.  
  19.   // Собираем первое окно
  20.   ll cap = 0;
  21.   ll len = 0;
  22.   for (; e < n; ++e) {
  23.     if (len + l[e] <= limit) {
  24.       len += l[e];
  25.       cap += c[e] * l[e];
  26.     } else {
  27.       part_e = limit - len;
  28.       cap += c[e] * part_e;
  29.       break;
  30.     }
  31.   }
  32.  
  33.   ll max_cap = cap;
  34.   while (e < n) {
  35.     if (l[b] - part_b <= l[e] - part_e) {
  36.       ll shift = l[b] - part_b;
  37.       cap += shift * c[e] - shift * c[b];
  38.       part_e += shift;
  39.       if (part_e == l[e]) {++e; part_e = 0;}
  40.       ++b;
  41.       part_b = 0;
  42.     } else {
  43.       ll shift = l[e] - part_e;
  44.       cap += shift * c[e] - shift * c[b];
  45.       part_b += shift;
  46.       ++e;
  47.       part_e = 0;
  48.     }
  49.     max_cap = std::max(max_cap, cap);
  50.   }
  51.  
  52.   std::cout << max_cap << std::endl;
  53.   return 0;
  54. }
  55.  
RAW Paste Data