結果
問題 | No.973 余興 |
ユーザー | leaf_1415 |
提出日時 | 2020-01-18 03:54:59 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,253 bytes |
コンパイル時間 | 414 ms |
コンパイル使用メモリ | 61,056 KB |
実行使用メモリ | 315,600 KB |
最終ジャッジ日時 | 2023-09-08 15:10:42 |
合計ジャッジ時間 | 33,948 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,081 ms
304,752 KB |
testcase_01 | AC | 1,097 ms
305,700 KB |
testcase_02 | AC | 1,074 ms
304,900 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 1,085 ms
305,380 KB |
testcase_06 | AC | 1,079 ms
304,708 KB |
testcase_07 | AC | 1,082 ms
305,312 KB |
testcase_08 | AC | 1,074 ms
304,292 KB |
testcase_09 | AC | 1,081 ms
304,708 KB |
testcase_10 | AC | 1,039 ms
298,440 KB |
testcase_11 | AC | 340 ms
166,868 KB |
testcase_12 | AC | 339 ms
166,280 KB |
testcase_13 | AC | 335 ms
165,772 KB |
testcase_14 | AC | 335 ms
165,680 KB |
testcase_15 | WA | - |
testcase_16 | AC | 51 ms
52,468 KB |
testcase_17 | AC | 32 ms
41,744 KB |
testcase_18 | AC | 41 ms
47,004 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 51 ms
52,276 KB |
testcase_22 | AC | 50 ms
52,236 KB |
testcase_23 | AC | 41 ms
47,024 KB |
testcase_24 | WA | - |
testcase_25 | AC | 21 ms
33,800 KB |
testcase_26 | AC | 31 ms
41,684 KB |
testcase_27 | AC | 57 ms
57,332 KB |
testcase_28 | AC | 41 ms
47,000 KB |
testcase_29 | WA | - |
testcase_30 | AC | 908 ms
304,204 KB |
testcase_31 | AC | 907 ms
304,200 KB |
testcase_32 | AC | 906 ms
304,076 KB |
testcase_33 | AC | 904 ms
304,036 KB |
testcase_34 | AC | 904 ms
303,428 KB |
testcase_35 | AC | 905 ms
303,560 KB |
testcase_36 | AC | 886 ms
299,192 KB |
testcase_37 | AC | 880 ms
298,464 KB |
testcase_38 | AC | 909 ms
303,904 KB |
testcase_39 | AC | 910 ms
303,072 KB |
testcase_40 | AC | 2 ms
5,432 KB |
testcase_41 | AC | 2 ms
5,516 KB |
testcase_42 | AC | 2 ms
5,460 KB |
testcase_43 | AC | 2 ms
5,536 KB |
testcase_44 | AC | 2 ms
5,476 KB |
testcase_45 | AC | 4 ms
9,972 KB |
testcase_46 | AC | 504 ms
304,196 KB |
testcase_47 | AC | 491 ms
303,944 KB |
testcase_48 | AC | 531 ms
304,072 KB |
testcase_49 | AC | 459 ms
289,436 KB |
testcase_50 | AC | 507 ms
302,320 KB |
testcase_51 | AC | 503 ms
304,000 KB |
testcase_52 | AC | 1,043 ms
304,076 KB |
testcase_53 | AC | 1,007 ms
301,840 KB |
testcase_54 | AC | 1,026 ms
304,064 KB |
testcase_55 | AC | 1,026 ms
315,356 KB |
ソースコード
#include <iostream> #include <algorithm> #define llint long long #define inf 1e18 using namespace std; llint n, x; llint a[5005], sum[5005]; llint dp[5005][5005], dpsum[5005][5005]; llint get(llint sl, llint sr, llint tl, llint tr) { return dpsum[tl][tr] - dpsum[tl][sr-1] - dpsum[sl+1][tr] + dpsum[sl+1][sr-1]; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> x; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i]; for(int l = n; l >= 1; l--){ for(int r = 1; r <= n; r++){ if(r-l < 0) continue; llint res = 0; llint p = upper_bound(sum, sum+n+1, sum[l-1]+x) - sum; if(p > r) res++; else res += get(l+1, r, p, r); //cout << l << " " << r << " " << p << endl; p = lower_bound(sum, sum+n+1, sum[r]-x) - sum; if(p < l) res++; else res += get(l, p, l, r-1); //cout << l << " " << r << " " << p << endl; if(res > 0) dp[l][r] = 0; else dp[l][r] = 1; dpsum[l][r] = dpsum[l+1][r] + dpsum[l][r-1] - dpsum[l+1][r-1] + dp[l][r]; } } /*for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout <<dp[i][j]<< " "; } cout << endl; }*/ if(dp[1][n]) cout << "A" << endl; else cout << "B" << endl; return 0; }