結果
| 問題 | No.973 余興 |
| ユーザー |
 QCFium
|
| 提出日時 | 2020-01-17 22:15:34 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 2,743 bytes |
| コンパイル時間 | 2,208 ms |
| コンパイル使用メモリ | 184,100 KB |
| 実行使用メモリ | 1,356,032 KB |
| 最終ジャッジ日時 | 2024-06-25 20:56:01 |
| 合計ジャッジ時間 | 8,999 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| 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 | -- | - |
ソースコード
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
struct SegTreeAny {
std::vector<bool> data;
int n;
SegTreeAny (int n_) {
for (n = 1; n < n_; n <<= 1);
data.resize(n << 1);
}
void set(int i, int val) {
for (data[i += n] = val; i >>= 1; ) data[i] = data[i << 1] || data[i << 1 | 1];
}
bool any(int l, int r) {
bool res = false;
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;
}
};
struct SegTreeAll {
std::vector<int> 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));
std::vector<SegTreeAny> r2(n + 1, SegTreeAny(n + 1));
std::vector<SegTreeAny> r3(n + 1, SegTreeAny(n + 1));
bool dp[n + 1][n + 1][2];
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= n; i++) {
dp[i][i][0] = true;
r0[i].set(i, true);
r1[i].set(i, true);
dp[i][i][1] = false;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j + i <= n; j++) {
int k = j + i;
dp[j][k][1] = true;
// 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][1] = false;
}
if (j < right[j] && r3[k].any(j + 1, right[j] + 1)) {
dp[j][k][0] = true;
}
// eat right -> dp[j][[left[k], k)]
if (left[k] < k && r0[j].all(left[k], k)) {
dp[j][k][1] = false;
}
if (left[k] < k && r2[j].any(left[k], k)) {
dp[j][k][0] = true;
}
r0[j].set(k, dp[j][k][0]);
r1[k].set(j, dp[j][k][0]);
r2[j].set(k, dp[j][k][1]);
r3[k].set(j, dp[j][k][1]);
}
}
/*
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;
}
}*/
std::cout << (dp[0][n][0] ? "A" : "B") << std::endl;
return 0;
}