結果
問題 |
No.1961 Clear Brackets
|
ユーザー |
![]() |
提出日時 | 2022-05-15 17:58:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,762 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 206,676 KB |
最終ジャッジ日時 | 2025-01-29 08:17:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 19 WA * 23 |
ソースコード
#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(r, min_l[r] + 1), 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; }