Advertisement
Guest User

Untitled

a guest
Oct 10th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <cstdio>
  2. #include <climits>
  3. #include <iostream>
  4.  
  5. #include <vector>
  6. #include <map>
  7.  
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12.  
  13. int n;
  14. ll a, b;
  15. ll T;
  16.  
  17. vector<bool> vOr;
  18.  
  19. vector<ll> pref;
  20. vector<ll> suf;
  21.  
  22. ll getAns(int l, int r){
  23.     ll ar = 0;
  24.     if(r == 0 || l < 0) ar = 0;
  25.     else ar = min((l+1)*a,r*a);
  26.     return (l >= 0 ? suf[l]: 0) + pref[r] + ar;
  27. }
  28.  
  29. int32_t main(){
  30.     cin >> n >> a >> b >> T;
  31.    
  32.     vOr.resize(n);
  33.     pref.resize(n);
  34.     suf.resize(n);
  35.  
  36.     char c;
  37.     for(int i = 0; i < n; i++){
  38.         cin >> c;
  39.         vOr[i] = (c=='w');
  40.     }
  41.  
  42.     for(int i = 0; i < n; i++){
  43.         pref[i] = (i > 0 ? a: 0) + (vOr[i] ? b: 0) + 1;
  44.         if(i) pref[i] += pref[i-1];
  45.     }
  46.  
  47.     ll lv = 0;
  48.     for(int i = n-1; i >= 0; i--){
  49.         suf[n-1-i] = a + (vOr[i] ? b: 0) + 1 + lv;
  50.         lv = suf[n-1-i];
  51.     }
  52.    
  53.     int ans = 0;
  54.     int lp = n-1;
  55.     for(int rp = 0; rp < n; rp++){
  56.         while(getAns(lp,rp) > T && lp >= 0){
  57.             lp--;
  58.         }  
  59.         if(getAns(lp,rp) <= T)ans = max(ans, max(0,lp+1)+rp+1);
  60.     }
  61.     cout << min(ans,n) << endl;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement