CodeForces 651D – Watchmen [二分]




Vasya’s telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.

For each photo it is known which orientation is intended for it — horizontal or vertical. Phone is in the vertical orientation and can’t be rotated. It takes b second to change orientation of the photo.

Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn’t spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.

Help Vasya find the maximum number of photos he is able to watch during T seconds.








#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 512000;
ll N, A, B, T;
ll s[maxn];
char str[maxn];

bool judge(ll sum) {
    for(ll i = 1; i <= sum; ++i) {
        ll t1 = s[i] + (s[N] - s[N - (sum - i)]);
        ll t2 = min(i - 1 + sum - 1, sum - i + sum - 1) * A;
        if(t1 + t2 + sum <= T)
            return true;
    return false;

int main() {
    cin >> N >> A >> B >> T >> str + 1;
    for(int i = 1; i <= N; ++i)
        s[i] = s[i-1] + B * (str[i] == 'w');
    ll L = 0, R = N, ok = 0;
    while(L <= R) {
        ll mid = L + (R - L) / 2;
        if(judge(mid)) {
            ok = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
    cout << ok << endl;
    return 0;