結果

問題 No.935 う　し　た　ぷ　に　き　あ く ん 笑　ビ　－　ム
コンテスト
ユーザー CleyL
提出日時 2022-08-18 15:59:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 924 bytes
コンパイル時間 681 ms
コンパイル使用メモリ 77,592 KB
最終ジャッジ日時 2025-01-30 23:51:09
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    string s;cin>>n>>s;
    vector<long long> A(n);
    vector<long long> B(n+1);
    vector<long long> C(n+1);
    for(int i = 0; n > i; i++){
        cin>>A[i];
        B[i+1] = B[i]+A[i];
        if(s[i] == 'E')C[i+1] = C[i]+1;
        else C[i+1] = C[i];
    }
    vector<long long> ans(n+1,1000000100);
    ans[0] = 0;
    for(int i = 0; n > i; i++){
        for(int j = i; n > j; j++){
            long long v = B[j+1]-B[i];
            int c = C[j+1]-C[i];
            ans[c] = min(ans[c],v);
        }
    }
    long long mn = ans[n];
    for(int i = n; 0 <= i; i--){
        ans[i] = min(mn,ans[i]);
        mn = min(mn,ans[i]);
    } 
    int q;cin>>q;
    for(int i = 0; q > i; i++){
        int x;cin>>x;
        auto z = upper_bound(ans.begin(),ans.end(),x);
        cout << z-ans.begin()-1 << endl;
    }
}
0