Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <climits>
- #include <iostream>
- #include <vector>
- #include <map>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- int n;
- ll a, b;
- ll T;
- vector<bool> vOr;
- vector<ll> pref;
- vector<ll> suf;
- ll getAns(int l, int r){
- ll ar = 0;
- if(r == 0 || l < 0) ar = 0;
- else ar = min((l+1)*a,r*a);
- return (l >= 0 ? suf[l]: 0) + pref[r] + ar;
- }
- int32_t main(){
- cin >> n >> a >> b >> T;
- vOr.resize(n);
- pref.resize(n);
- suf.resize(n);
- char c;
- for(int i = 0; i < n; i++){
- cin >> c;
- vOr[i] = (c=='w');
- }
- for(int i = 0; i < n; i++){
- pref[i] = (i > 0 ? a: 0) + (vOr[i] ? b: 0) + 1;
- if(i) pref[i] += pref[i-1];
- }
- ll lv = 0;
- for(int i = n-1; i >= 0; i--){
- suf[n-1-i] = a + (vOr[i] ? b: 0) + 1 + lv;
- lv = suf[n-1-i];
- }
- int ans = 0;
- int lp = n-1;
- for(int rp = 0; rp < n; rp++){
- while(getAns(lp,rp) > T && lp >= 0){
- lp--;
- }
- if(getAns(lp,rp) <= T)ans = max(ans, max(0,lp+1)+rp+1);
- }
- cout << min(ans,n) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement