結果

問題 No.935 う　し　た　ぷ　に　き　あ く ん 笑　ビ　－　ム
コンテスト
ユーザー kappybar
提出日時 2020-03-27 19:25:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,516 bytes
コンパイル時間 1,587 ms
コンパイル使用メモリ 172,324 KB
実行使用メモリ 112,208 KB
最終ジャッジ日時 2025-01-02 09:14:45
合計ジャッジ時間 52,138 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 35 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
 
int main() {
        int n;
        cin >>  n;
        string s;
        cin >> s;
        vector<int> mon(n+1);
        vector<int> a(n+1);
        rep(i,n) cin >> a[i+1];
        rep(i,n) a[i+1] += a[i];
        rep(i,n){
                if(s[i] == 'E') mon[i+1] ++;
        }
        rep(i,n) mon[i+1] += mon[i];

        map<int,int> mp;
        for(int i=0;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                        int key = a[j] - a[i];
                        int value = mon[j] - mon[i];
                        mp[key] = max(mp[key],value);
                }
        }

        int before = -1;
        for(auto it = mp.begin();it !=mp.end();it++){
                if(it->second < before) it->second = before; 
                else before = it->second;
        }
        
        vector<pp> num = {pp(0,0)};
        for(auto p:mp){
                num.push_back(pp(p.first,p.second));
        }

        int q;
        cin >> q;
        rep(i,q){
                int k;
                cin >> k;
                int l = -1,r = num.size();
                while(r - l > 1){
                        int m = (l + r)/2;
                        if(num[m].first <= k) l = m;
                        else r = m;
                }
                cout << num[l].second << endl;
        }




        return 0;
}
0