う し た ぷ に き あ く ん 笑 ビ － ム [yukicoder 935]

https://yukicoder.me/problems/no/935

• 尺取法

解説

https://yukicoder.me/submissions/402911

んーと思って見てると制約が弱めなことに気がつく。
よって、O(NQ)はまずできそう。
つまり、ビームの始点は全探索可能。
始点からビームでどこまで伸ばせるかを考えていくが、これは尺取法でうまいことやれる。
尺取法がわからないと少し厳しいかもしれない。
ビームの始点終点は特に逆になってても関係ないので、最大区間を考えていけばいい。

int N; string S;
int A[2010], Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) cin >> A[i];
    cin >> Q;
    rep(_, 0, Q) {
        int K; cin >> K;

        int tot = 0, L = 0, ans = 0, enemy = 0;
        rep(R, 0, N) {
            tot += A[R];
            if (S[R] == 'E') enemy++;

            while (K < tot) {
                tot -= A[L];
                if (S[L] == 'E') enemy--;
                L++;
            }

            chmax(ans, enemy);
        }

        printf("%d\n", ans);
    }
}