Advertisement
PikMike

Untitled

Dec 11th, 2016
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define sz(x) (int)(x).size()
  6. #define li long long
  7. #define ld long double
  8. #define x first
  9. #define y second
  10. #define pt pair<int, int>
  11. #define pll pair<ll, ll>
  12. #define forn(i, t) for(int i = 0; i < (t); i++)
  13. #define fore(i, f, t) for(int i = (f); i < (t); i++)
  14. #define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
  15. #define all(x) (x).begin(), (x).end()
  16. #define ins insert
  17.  
  18. using namespace std;
  19.  
  20.  
  21. const int INF = 1e9;
  22. const int MOD = 1e9 + 7;
  23. const li INF64 = 1e18;
  24. const ld EPS = 1e-7;
  25.  
  26. mt19937 myrand(time(NULL));
  27.  
  28. const int N = 200 * 1000 + 13;
  29.  
  30. int n, w, d;
  31. pt a[N];
  32.  
  33.  
  34. bool read(){
  35.     if(scanf("%d%d%d", &n, &w, &d) != 3)
  36.         return 0;
  37.     forn(i, n)
  38.         scanf("%d", &a[i].y);
  39.     forn(i, n)
  40.         scanf("%d", &a[i].x);
  41.     return 1;
  42. }
  43.  
  44.  
  45. void solve(){
  46.     multiset<pt> cur, cura;
  47.     int ans = 0;
  48.     int sum = 0, suma = 0, l = 0, res = 0;
  49.     forn(i, n){
  50.         cur.insert(a[i]);
  51.         sum += a[i].x;
  52.         res += a[i].y;
  53.         while (sum + suma > d){
  54.             if (sz(cura) < w && !cur.empty()){
  55.                 pt tmp = *cur.rbegin();
  56.                 cura.insert(tmp);
  57.                 sum -= tmp.x;
  58.                 sum += (tmp.x + 1) / 2;
  59.                 cur.erase(cur.find(tmp));
  60.                 continue;
  61.             }
  62.             if (cur.find(a[l]) != cur.end()){
  63.                 cur.erase(cur.find(a[l]));
  64.                 sum -= a[l].x;
  65.             }
  66.             else if (cura.find(a[l]) != cur.end()){
  67.                 cura.erase(cura.find(a[l]));
  68.                 suma -= (a[l].x + 1) / 2;
  69.             }
  70.             res -= a[l].y;
  71.             l++;
  72.         }
  73.         ans = max(ans, res);
  74.     }
  75.     printf("%d\n", ans);
  76. }
  77.  
  78.  
  79. int main(){
  80.     #ifdef _DEBUG
  81.         freopen("input.txt", "r", stdin);
  82.     #endif
  83.     while(read())
  84.         solve();
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement