QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136840 | #236. Balanced Sequence | wtn135687# | 100 ✓ | 37ms | 6680kb | C++20 | 1.9kb | 2023-08-09 12:38:42 | 2023-08-09 12:38:43 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5+10,mo = 1e9+7;
struct node1{
int l,r;
bool operator<(const node1 &T)const{
if(min(l,T.r)==min(T.l,r)){
return l>T.l;
}
return min(l,T.r)>min(T.l,r );
}
}a[N];
struct node2{
int l,r;
bool operator<(const node2 &T)const{
if(T.l+max(0ll,(l-T.r))==(l+max(0ll,T.l-r ))){
return l<T.l;
}
return (T.l+max(0ll,(l-T.r))>(l+max(0ll,T.l-r )));
}
}b[N];
int ans=0,t1,t2,sum=0;
void calc(string s,int i){
int cnt_l=0,cnt_r=0;
t1=0,t2=0;
for(auto t:s){
if(t=='('){
cnt_l++;
continue;
}
if(t==')'){
if(cnt_l>0){
--cnt_l,ans+=2;
}else{
cnt_r++;
}
}
}
sum+=cnt_l;
a[i]={cnt_l,cnt_r};
b[i]={cnt_l,cnt_r};
}
void init(int n){
sum=0;
for(int i=1;i<=n;++i){
a[i]={0,0};
b[i]={0,0};
}
}
inline void solve(){
int n;
cin>>n;
init(n);
ans=0;
for(int i=1;i<=n;++i){
string s;
cin>>s;
calc(s,i);
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int L=0,R=0,res=0,t=0;
for(int i=1;i<=n;++i){
res+=min(L,a[i].r);
L=max(0ll,L-a[i].r);
L+=a[i].l;
// cout<<"res->"<<res<<" l->"<<L<<endl;
}
// L=0,R=0;
// for(int i=1;i<=n;++i){
// L+=b[i].l;
// t=max(L,t);
// L-=b[i].r;
// }
// cout<<"sum->"<<sum<<"res->"<<res<<" t->"<<t<<endl;
cout<<(ans+(res)*2)<<endl;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int WTN666=1;cin>>WTN666;
while(WTN666--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 37ms
memory: 6680kb
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