結果

問題 No.973 余興
ユーザー QCFiumQCFium
提出日時 2020-08-01 00:57:32
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 261 ms
28,160 KB
testcase_01 AC 283 ms
28,104 KB
testcase_02 AC 260 ms
28,116 KB
testcase_03 AC 274 ms
28,076 KB
testcase_04 AC 272 ms
28,172 KB
testcase_05 AC 275 ms
27,996 KB
testcase_06 AC 274 ms
28,004 KB
testcase_07 AC 274 ms
28,084 KB
testcase_08 AC 297 ms
27,900 KB
testcase_09 AC 277 ms
28,100 KB
testcase_10 AC 254 ms
27,036 KB
testcase_11 AC 62 ms
12,516 KB
testcase_12 AC 70 ms
12,532 KB
testcase_13 AC 67 ms
12,264 KB
testcase_14 AC 64 ms
12,296 KB
testcase_15 AC 13 ms
6,944 KB
testcase_16 AC 12 ms
6,940 KB
testcase_17 AC 8 ms
6,940 KB
testcase_18 AC 10 ms
6,940 KB
testcase_19 AC 11 ms
6,940 KB
testcase_20 AC 8 ms
6,944 KB
testcase_21 AC 12 ms
6,944 KB
testcase_22 AC 13 ms
6,940 KB
testcase_23 AC 10 ms
6,944 KB
testcase_24 AC 11 ms
6,940 KB
testcase_25 AC 6 ms
6,944 KB
testcase_26 AC 9 ms
6,940 KB
testcase_27 AC 14 ms
6,940 KB
testcase_28 AC 10 ms
6,944 KB
testcase_29 AC 10 ms
6,940 KB
testcase_30 AC 245 ms
27,980 KB
testcase_31 AC 261 ms
28,116 KB
testcase_32 AC 261 ms
28,120 KB
testcase_33 AC 264 ms
28,144 KB
testcase_34 AC 253 ms
27,988 KB
testcase_35 AC 252 ms
28,296 KB
testcase_36 AC 243 ms
27,324 KB
testcase_37 AC 239 ms
27,352 KB
testcase_38 AC 255 ms
27,928 KB
testcase_39 AC 270 ms
27,920 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 1 ms
6,944 KB
testcase_42 AC 2 ms
6,944 KB
testcase_43 AC 2 ms
6,940 KB
testcase_44 AC 2 ms
6,940 KB
testcase_45 AC 2 ms
6,944 KB
testcase_46 AC 249 ms
28,220 KB
testcase_47 AC 250 ms
28,176 KB
testcase_48 AC 251 ms
28,048 KB
testcase_49 AC 227 ms
26,104 KB
testcase_50 AC 243 ms
27,960 KB
testcase_51 AC 252 ms
28,156 KB
testcase_52 AC 286 ms
27,972 KB
testcase_53 AC 239 ms
27,676 KB
testcase_54 AC 247 ms
28,092 KB
testcase_55 AC 259 ms
28,100 KB
権限があれば一括ダウンロードができます

ソースコード

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