651D - Image Preview - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define all(x) x.begin(),x.end()  
#define allr(x) x.rbegin(),x.rend() 
#define print(a) for(auto e:a) cout<<e<<" ";cout<<endl; 
#define cr(_) {cout<<_<<endl;return;}
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"
#define s second  
#define f first
#define pb push_back
#define sz(a) a.size()
const ll N=1e5+5;
const ll MOD=998244353;
using namespace std;

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
void solve(){
ll n,a,b,c;
cin>>n>>a>>b>>c;
string s;
cin>>s;
vl pre(n+1);
rep(i,1,n+1){
    pre[i]=(s[i-1]=='w'?b+1:1);

}
rep(i,1,n+1) pre[i]+=pre[i-1];

ll l=0;
ll r=n;
ll res=0;
while(l<=r){
    ll mid=(l+r)/2;
    ll ok=0;
    rep(i,1,mid+1){
        ll sum=pre[i]+pre[n]-pre[n-mid+i];
        ll sum1=min(2*(i-1)*a+(mid-i)*a,2*(mid-i)*a+(i-1)*a);
        if(sum+sum1<=c){
            ok=1;
        }
    }
    if(ok){
        res=mid;
        l=mid+1;
    }
    else r=mid-1;
    
}
cout<<res<<endl;

}



int main() {
    int t=1;
 //  cin >> t;

    while (t--) {
      solve();
    }

    return 0;
}