#418961 (C++14) No.973 余興

提出ソース

結果

問題	No.973 余興
ユーザー	QCFium
提出日時	2020-01-17 22:47:44
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	1,975 bytes
コンパイル時間	2,332 ms
コンパイル使用メモリ	189,340 KB
実行使用メモリ	96,852 KB
最終ジャッジ日時	2023-09-08 05:48:24
合計ジャッジ時間	56,809 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3,304 ms 96,852 KB
testcase_01	AC	3,304 ms 48,356 KB
testcase_02	AC	3,269 ms 48,260 KB
testcase_03	AC	3,299 ms 48,208 KB
testcase_04	AC	3,320 ms 48,336 KB
testcase_05	AC	3,263 ms 48,240 KB
testcase_06	AC	3,236 ms 48,192 KB
testcase_07	AC	3,238 ms 48,324 KB
testcase_08	AC	3,345 ms 47,984 KB
testcase_09	AC	3,340 ms 48,336 KB
testcase_10	AC	3,267 ms 46,768 KB
testcase_11	AC	1,784 ms 18,428 KB
testcase_12	AC	1,777 ms 18,396 KB
testcase_13	AC	1,772 ms 18,280 KB
testcase_14	AC	1,757 ms 18,276 KB
testcase_15	AC	81 ms 4,992 KB
testcase_16	AC	83 ms 5,076 KB
testcase_17	AC	52 ms 4,756 KB
testcase_18	AC	66 ms 4,736 KB
testcase_19	AC	67 ms 4,784 KB
testcase_20	AC	50 ms 4,532 KB
testcase_21	AC	82 ms 5,048 KB
testcase_22	AC	82 ms 5,056 KB
testcase_23	AC	67 ms 4,712 KB
testcase_24	AC	67 ms 4,856 KB
testcase_25	AC	31 ms 4,380 KB
testcase_26	AC	50 ms 4,732 KB
testcase_27	AC	102 ms 5,720 KB
testcase_28	AC	66 ms 4,792 KB
testcase_29	AC	66 ms 4,772 KB
testcase_30	TLE	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

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

struct SegTreeAll {
	std::vector<bool> data;
	int n;
	SegTreeAll (int n_) {
		for (n = 1; n < n_; n <<= 1);
		data.resize(n << 1);
		for (int i = n_; i < n; i++) data[i + n] = true;
		for (int i = n - 1; i; i--) data[i] = data[i << 1] && data[i << 1 | 1];
	}
	void set(int i, int val) {
		for (data[i += n] = val; i >>= 1; ) data[i] = data[i << 1] && data[i << 1 | 1];
	}
	bool all(int l, int r) {
		int res = true;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res &= data[--r];
			if (l & 1) res &= data[l++];
		}
		return res;
	}
};

int main() {
	int n = ri(), 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] = a[i] + sum[i];
	
	int left[n + 1], right[n + 1];
	for (int i = 0; i <= n; i++) {
		left[i] = std::lower_bound(sum, sum + n + 1, sum[i] - x) - sum;
		right[i] = std::upper_bound(sum, sum + n + 1, sum[i] + x) - sum - 1;
	}
	
	std::vector<SegTreeAll> r0(n + 1, SegTreeAll(n + 1));
	std::vector<SegTreeAll> r1(n + 1, SegTreeAll(n + 1));
	
	bool dp[n + 1][n + 1];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i <= n; i++) {
		dp[i][i] = true;
		r0[i].set(i, true);
		r1[i].set(i, true);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j + i <= n; j++) {
			int k = j + i;
			dp[j][k] = false;
			// dp[j][k][?]
			// eat left -> dp[j + 1, right[j]][k]
			if (j < right[j] && !r1[k].all(j + 1, right[j] + 1)) {
				dp[j][k] = true;
			}
			// eat right -> dp[j][[left[k], k)]
			if (left[k] < k && !r0[j].all(left[k], k)) {
				dp[j][k] = true;
			}
			r0[j].set(k, dp[j][k]);
			r1[k].set(j, dp[j][k]);
		}
	}
	/*
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			std::cerr << i << "," << j << " : " << dp[i][j][0] << "," << dp[i][j][1] << std::endl;
		}
	}*/
	puts(dp[0][n] ? "A" : "B");
	return 0;
}

yukicoder

結果

テストケース

ソースコード