結果

問題 No.935 う　し　た　ぷ　に　き　あ く ん 笑　ビ　－　ム
ユーザー wunderkammer2wunderkammer2
提出日時 2019-12-08 11:03:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,487 bytes
コンパイル時間 863 ms
コンパイル使用メモリ 96,100 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-12 06:44:19
合計ジャッジ時間 2,942 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,348 KB
testcase_01 AC 4 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 4 ms
4,352 KB
testcase_04 AC 5 ms
4,348 KB
testcase_05 AC 3 ms
4,348 KB
testcase_06 AC 6 ms
4,352 KB
testcase_07 AC 6 ms
4,348 KB
testcase_08 AC 9 ms
4,348 KB
testcase_09 AC 7 ms
4,352 KB
testcase_10 AC 7 ms
4,352 KB
testcase_11 AC 8 ms
4,348 KB
testcase_12 AC 1 ms
4,352 KB
testcase_13 AC 1 ms
4,352 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 AC 9 ms
4,348 KB
testcase_18 AC 5 ms
4,348 KB
testcase_19 AC 6 ms
4,352 KB
testcase_20 AC 7 ms
4,348 KB
testcase_21 AC 3 ms
4,352 KB
testcase_22 AC 3 ms
4,352 KB
testcase_23 AC 1 ms
4,352 KB
testcase_24 AC 2 ms
4,352 KB
testcase_25 AC 2 ms
4,348 KB
testcase_26 AC 2 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 2 ms
4,348 KB
testcase_29 AC 2 ms
4,348 KB
testcase_30 AC 2 ms
4,352 KB
testcase_31 AC 2 ms
4,352 KB
testcase_32 AC 2 ms
4,352 KB
testcase_33 AC 7 ms
4,348 KB
testcase_34 AC 8 ms
4,352 KB
testcase_35 AC 7 ms
4,348 KB
testcase_36 AC 4 ms
4,348 KB
testcase_37 AC 6 ms
4,348 KB
testcase_38 AC 6 ms
4,348 KB
testcase_39 AC 8 ms
4,352 KB
testcase_40 AC 8 ms
4,352 KB
testcase_41 AC 8 ms
4,348 KB
testcase_42 AC 7 ms
4,348 KB
testcase_43 AC 8 ms
4,348 KB
testcase_44 AC 5 ms
4,348 KB
testcase_45 AC 8 ms
4,348 KB
testcase_46 AC 3 ms
4,352 KB
testcase_47 AC 5 ms
4,352 KB
testcase_48 AC 6 ms
4,348 KB
testcase_49 AC 5 ms
4,348 KB
testcase_50 AC 6 ms
4,352 KB
testcase_51 AC 6 ms
4,348 KB
testcase_52 AC 6 ms
4,348 KB
testcase_53 AC 8 ms
4,352 KB
testcase_54 AC 5 ms
4,348 KB
testcase_55 AC 2 ms
4,348 KB
testcase_56 AC 7 ms
4,348 KB
testcase_57 AC 6 ms
4,352 KB
testcase_58 AC 2 ms
4,352 KB
testcase_59 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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