結果

問題 No.973 余興
ユーザー QCFium
提出日時 2020-08-01 00:57:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 297 ms / 4,000 ms
コード長 1,022 bytes
コンパイル時間 1,581 ms
コンパイル使用メモリ 167,848 KB
実行使用メモリ 28,296 KB
最終ジャッジ日時 2024-07-06 23:16:48
合計ジャッジ時間 11,715 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int x = ri();
	int a[n];
	for (auto &i : a) i = ri();
	
	int64_t sum[n + 1];
	sum[0] = 0;
	for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + a[i];
	
	bool dp[n + 1][n + 1];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i <= n; i++) dp[i][i] = false;
	int tail0[n + 1], tail1[n + 1];
	int cur_sum0[n + 1], cur_sum1[n + 1];
	for (int i = 0; i <= n; i++) {
		tail0[i] = tail1[i] = i;
		cur_sum0[i] = cur_sum1[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n - i; j++) {
			cur_sum0[j + i] += dp[j + 1][j + i];
			while (tail0[j + i] > j && sum[tail0[j + i]] - sum[j] > x)
				cur_sum0[j + i] -= dp[tail0[j + i]--][j + i];
			dp[j][j + i] |= cur_sum0[j + i];
			
			cur_sum1[j] += dp[j][j + i - 1];
			while (tail1[j] < j + i && sum[j + i] - sum[tail1[j]] > x)
				cur_sum1[j] -= dp[j][tail1[j]++];
			dp[j][j + i] |= cur_sum1[j];
			dp[j][j + i] ^= 1;
		}
	}
	puts(dp[0][n] ? "B" : "A");
	return 0;
}
0