結果
問題 | No.973 余興 |
ユーザー | QCFium |
提出日時 | 2020-01-17 22:47:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,975 bytes |
コンパイル時間 | 2,510 ms |
コンパイル使用メモリ | 191,388 KB |
実行使用メモリ | 53,888 KB |
最終ジャッジ日時 | 2024-06-25 23:01:38 |
合計ジャッジ時間 | 52,455 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3,035 ms
53,888 KB |
testcase_01 | AC | 3,051 ms
48,384 KB |
testcase_02 | AC | 3,011 ms
48,296 KB |
testcase_03 | AC | 3,065 ms
48,384 KB |
testcase_04 | AC | 3,054 ms
48,320 KB |
testcase_05 | AC | 3,077 ms
48,548 KB |
testcase_06 | AC | 3,066 ms
48,512 KB |
testcase_07 | AC | 3,041 ms
48,512 KB |
testcase_08 | AC | 3,084 ms
48,384 KB |
testcase_09 | AC | 3,078 ms
48,484 KB |
testcase_10 | AC | 2,961 ms
46,976 KB |
testcase_11 | AC | 1,676 ms
18,596 KB |
testcase_12 | AC | 1,651 ms
18,524 KB |
testcase_13 | AC | 1,652 ms
18,504 KB |
testcase_14 | AC | 1,660 ms
18,388 KB |
testcase_15 | AC | 74 ms
5,376 KB |
testcase_16 | AC | 76 ms
5,376 KB |
testcase_17 | AC | 47 ms
5,376 KB |
testcase_18 | AC | 61 ms
5,376 KB |
testcase_19 | AC | 62 ms
5,376 KB |
testcase_20 | AC | 47 ms
5,376 KB |
testcase_21 | AC | 76 ms
5,376 KB |
testcase_22 | AC | 73 ms
5,376 KB |
testcase_23 | AC | 58 ms
5,376 KB |
testcase_24 | AC | 61 ms
5,376 KB |
testcase_25 | AC | 28 ms
5,376 KB |
testcase_26 | AC | 45 ms
5,376 KB |
testcase_27 | AC | 94 ms
6,016 KB |
testcase_28 | AC | 59 ms
5,376 KB |
testcase_29 | AC | 59 ms
5,376 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 | -- | - |
ソースコード
#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;}