QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136784 | #236. Balanced Sequence | kiwiHM# | 100 ✓ | 37ms | 4872kb | C++14 | 1.2kb | 2023-08-09 11:23:20 | 2023-08-09 11:23:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
int stk[maxn];
char buf[maxn];
inline bool cmp(const pair<int, int> &p, const pair<int, int> &q){
if((p.first > p.second) != (q.first > q.second)) return (p.first > p.second);
if(p.first > p.second) return p.second < q.second;
return p.first > q.first;
}
inline void solve(){
scanf("%d", &n);
int ans = 0;
vector<pair<int, int> > vec;
for(int i = 0; i < n; ++i){
scanf("%s", buf); int len = strlen(buf);
int top = 0;
for(int j = 0; j < len; ++j){
if(buf[j] == '(') stk[++top] = '(';
else{
if(top && stk[top] == '(') --top, ++ans;
else stk[++top] = ')';
}
}
int x = 0, y = 0;
for(int j = 1; j <= top; ++j) x += (stk[j] == '('), y += (stk[j] == ')');
vec.push_back(make_pair(x, y));
}
sort(vec.begin(), vec.end(), cmp);
int rig = 0;
for(int i = 0; i < vec.size(); ++i){
// printf("left: %d right: %d\n", vec[i].first, vec[i].second);
int cur = min(rig, vec[i].second);
ans += cur, rig -= cur;
rig += vec[i].first;
}
printf("%d\n", ans * 2);
}
int main(){
int T;
for(scanf("%d", &T); T--; solve());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 37ms
memory: 4872kb
input:
482 2 ()())())())()(()))))(())()())))))))))))((()()()))(()()((((((())))(())()) ((())(((()(())())())()))))(( 2 (()(()))))())))))()(()))(())( ())(()()(()(()))(((()))))))())))))))))(()())()((()))()()))(()(()(((())) 1 ))())(())(())(()()()((())())(())))()(()(()(())()((()()()))()((()(()(((()))))(((((()(()...
output:
80 80 88 86 92 90 88 86 92 98 84 96 80 88 96 92 92 90 96 82 92 80 82 84 88 94 88 80 92 82 88 88 88 90 82 88 96 78 96 98 94 98 68 78 82 90 90 92 90 80 78 90 78 84 94 94 84 90 84 92 96 96 82 92 90 90 88 86 94 94 88 94 84 86 96 86 82 90 98 82 78 94 88 86 80 88 96 86 84 86 92 84 84 90 92 82 86 94 84 94 ...
result:
ok 482 lines