結果

問題 No.935 う　し　た　ぷ　に　き　あ く ん 笑　ビ　－　ム
ユーザー wunderkammer2
提出日時 2019-12-08 11:03:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,487 bytes
コンパイル時間 1,070 ms
コンパイル使用メモリ 97,784 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 06:04:08
合計ジャッジ時間 2,799 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

int main()
{
	int n;
	cin >> n;

	string s;
	cin >> s;

	vector<ll> as(n);
	rep(i, n) cin >> as[i];


	int q;
	cin >> q;

	vector<ll> ks(q);
	rep(i, q) cin >> ks[i];


	//Aと敵個数の累積和を計算
	vector<ll> acs(n + 1, 0);
	vector<int> ccs(n + 1, 0);


	rep(i, n)
	{
		acs[i + 1] = acs[i] + as[i];
		ccs[i + 1] = ccs[i];
		if (s[i] == 'E')
		{
			ccs[i + 1] += 1;
		}
	}


	//敵数tを倒すために必要なエネルギーの最小値を計算
	vector<ll> dp(n + 1, 1000000000);
	dp[0] = 0;
	rep(i, n)
	{
		reple(j, i + 1, n)
		{
			int t = ccs[j] - ccs[i];
			dp[t] = min(dp[t], acs[j] - acs[i]);
		}
	}


	for (auto k : ks)
	{

		//lb：条件をクリアできる
		int lb = -1;
		//ub：条件をクリアできない
		int ub = n + 1;

		while (ub - lb > 1)
		{
			int mid = (lb + ub) / 2;

			//mid体の敵を倒すのに必要な威力をk以下にできるか？
			if (dp[mid] <= k)
			{
				lb = mid;
			}
			else
			{
				ub = mid;
			}
		}

		cout << lb << endl;
	}

	return 0;
}
0