QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136713 | #236. Balanced Sequence | whsyhyyh# | 100 ✓ | 30ms | 4696kb | C++14 | 1.3kb | 2023-08-09 10:21:49 | 2023-08-09 10:21:56 |
Judging History
answer
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define N 100010
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define drep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int rd() {
int res=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return res*f;
}
int T,n;
char s[N];
struct node {
int l,r;
}q[N],p[N];int x,y;
bool cmpq(node x,node y) {
return x.r<y.r;
}
bool cmpp(node x,node y) {
return x.l>y.l;
}
int main() {
T=rd();
while(T--) {
n=rd();
int ans=0,x=0,y=0;
rep(i,1,n) {
scanf("%s",s+1);
int len=strlen(s+1),A=0,B=0;
rep(j,1,len) if(s[j]=='(') A++;else {
if(A) A--,ans+=2;else B++;
}
if(A>=B) q[++x]=(node) {A,B};
else p[++y]=(node) {A,B};
}
sort(q+1,q+x+1,cmpq);
sort(p+1,p+y+1,cmpp);
int A=0,B=0;
rep(i,1,x) {
int tmp=max(min(A,q[i].r),min(B,q[i].l));
ans+=2*tmp,A=A+q[i].l-tmp,B=B+q[i].r-tmp;
}
rep(i,1,y) {
int tmp=max(min(A,p[i].r),min(B,p[i].l));
ans+=2*tmp,A=A+p[i].l-tmp,B=B+p[i].r-tmp;
}
printf("%d\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 30ms
memory: 4696kb
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