結果
問題 | No.1961 Clear Brackets |
ユーザー | 👑 tute7627 |
提出日時 | 2022-05-15 17:48:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 1,750 bytes |
コンパイル時間 | 2,304 ms |
コンパイル使用メモリ | 211,376 KB |
実行使用メモリ | 24,056 KB |
最終ジャッジ日時 | 2023-10-11 05:52:56 |
合計ジャッジ時間 | 9,222 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,352 KB |
testcase_01 | AC | 2 ms
4,352 KB |
testcase_02 | AC | 2 ms
4,352 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,348 KB |
testcase_05 | AC | 1 ms
4,352 KB |
testcase_06 | AC | 2 ms
4,356 KB |
testcase_07 | AC | 2 ms
4,476 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,352 KB |
testcase_10 | AC | 2 ms
4,352 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,356 KB |
testcase_13 | AC | 1 ms
4,348 KB |
testcase_14 | AC | 119 ms
21,132 KB |
testcase_15 | AC | 111 ms
20,652 KB |
testcase_16 | AC | 83 ms
20,664 KB |
testcase_17 | AC | 115 ms
20,852 KB |
testcase_18 | AC | 105 ms
20,564 KB |
testcase_19 | AC | 75 ms
20,512 KB |
testcase_20 | AC | 110 ms
20,528 KB |
testcase_21 | AC | 71 ms
20,436 KB |
testcase_22 | AC | 83 ms
20,600 KB |
testcase_23 | AC | 110 ms
20,448 KB |
testcase_24 | AC | 52 ms
20,568 KB |
testcase_25 | AC | 127 ms
24,056 KB |
testcase_26 | AC | 98 ms
21,100 KB |
testcase_27 | AC | 103 ms
20,496 KB |
testcase_28 | AC | 65 ms
20,596 KB |
testcase_29 | AC | 139 ms
20,796 KB |
testcase_30 | AC | 100 ms
20,556 KB |
testcase_31 | AC | 66 ms
20,524 KB |
testcase_32 | AC | 98 ms
21,016 KB |
testcase_33 | AC | 90 ms
21,056 KB |
testcase_34 | AC | 112 ms
21,352 KB |
testcase_35 | AC | 103 ms
20,588 KB |
testcase_36 | AC | 123 ms
20,520 KB |
testcase_37 | AC | 128 ms
23,676 KB |
testcase_38 | AC | 126 ms
21,036 KB |
testcase_39 | AC | 107 ms
20,504 KB |
testcase_40 | AC | 131 ms
20,856 KB |
testcase_41 | AC | 99 ms
20,476 KB |
testcase_42 | AC | 99 ms
20,556 KB |
testcase_43 | AC | 99 ms
20,588 KB |
testcase_44 | AC | 98 ms
20,536 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/segtree> using namespace std; int op_min(int a, int b){ return min(a, b); } int e_min(){ return (int)(1e9); } int op_max(int a, int b){ return max(a, b); } int e_max(){ return (int)(-1e9); } int main(){ int N; cin >> N; string S; cin >> S; S += '?'; N++; vector<int>max_r(N + 1); { vector<int>B(N + 1); for(int i = 0; i < N; i++){ B[i + 1] = B[i] + (S[i] == ')' ? -1 : 1); } atcoder::segtree<int,op_min,e_min>seg(B); for(int i = 0; i < N; i++){ auto judge = [&](int x){ return x >= B[i]; }; max_r[i] = seg.max_right<decltype(judge)>(i, judge); } } vector<int>min_l(N + 1); { vector<int>B(N + 1); for(int i = 0; i < N; i++){ B[i + 1] = B[i] + (S[i] == '(' ? 1 : -1); } atcoder::segtree<int,op_min,e_min>seg(B); for(int i = 0; i < N; i++){ auto judge = [&](int x){ return x >= B[i]; }; min_l[i] = seg.min_left<decltype(judge)>(i, judge); } } using Seg = atcoder::segtree<int,op_max,e_max>; vector<Seg> dp1(2, Seg(N + 1)); vector<Seg> dp2(2, Seg(N + 1)); dp1[0].set(0,0); vector<vector<int>>del(N + 2); for(int i = 0; i < N; i++){ del[max_r[i]].push_back(i); } for(int r = 0; r < N; r++){ for(auto l: del[r]){ for(int j = 0; j < 2; j++){ dp1[j].set(l, e_max()); dp2[j].set(l, e_max()); } } int mx1 = max(dp1[r % 2].get(r), dp1[r % 2].prod(min_l[r], r) + 1); int mx2 = max(dp2[r % 2].get(r), dp2[r % 2].prod(min_l[r], r) + 1); if(S[r] != '(')dp1[(r + 1) % 2].set(r + 1, mx1); if(S[r] != ')')dp2[(r + 1) % 2].set(r + 1, max(mx1, mx2)); } cout << dp2[N % 2].get(N) << endl; return 0; }