QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #420989 | #236. Balanced Sequence | ship2077 | 100 ✓ | 35ms | 4388kb | C++14 | 957b | 2024-05-25 09:08:06 | 2024-05-25 09:08:08 |
Judging History
answer
#include<bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
int n,ans,cnt,lft,rht;
void solve(){ cin>>n;ans=cnt=0;
vector<pair<int,int>>vec1,vec2;
for (int i=1;i<=n;i++){
string str;cin>>str;
int len=str.length();lft=rht=0;
for (int j=0;j<len;j++)
if (str[j]=='(') lft++;
else if (lft) lft--,ans+=2;
else rht++;
if (lft>=rht) vec1.emplace_back(lft,rht);
else vec2.emplace_back(lft,rht);
}
sort(vec1.begin(),vec1.end(),[](const pair<int,int>a,const pair<int,int>b){return a.sec<b.sec;});
sort(vec2.begin(),vec2.end(),[](const pair<int,int>a,const pair<int,int>b){return a.fir>b.fir;});
for (auto [lft,rht]:vec1){
int mn=min(cnt,rht);
ans+=mn<<1;cnt+=lft-mn;
}
for (auto [lft,rht]:vec2){
int mn=min(cnt,rht);
ans+=mn<<1;cnt+=lft-mn;
}
printf("%d\n",ans);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin>>T; while (T--) solve(); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 35ms
memory: 4388kb
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