QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136816 | #236. Balanced Sequence | BoulevardDust# | 100 ✓ | 202ms | 4924kb | C++17 | 2.8kb | 2023-08-09 12:03:29 | 2023-08-09 12:03:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define out(x) cerr << #x << " = " << x << " "
#define outln(x) cerr << #x << " = " << x << endl
#define outarr(x, l, r) {cerr << #x"[" << l << "~" << r << "] = "; for (int _ = l; _ <= r; ++_) cerr << x[_] << " "; cerr << endl;}
const int N = 100005;
int T, n, m, answer = 0;
char s[N];
pii a[N];
int st[N];
int id[N];
pii get(char* s) {
int n = strlen(s + 1);
int tp = 0;
for(int i = 1; i <= n; ++i) {
if(s[i] == '(') {
st[++tp] = 0;
}
else {
if(tp > 0 && !st[tp]) {
--tp, answer += 2;
}
else {
st[++tp] = 1;
}
}
}
for(int i = 1; i <= tp; ++i) {
if(!st[i]) {
return make_pair(i - 1, tp - i + 1);
}
}
return make_pair(tp, 0);
}
int calc() {
int cb = 0, answer = 0;
for (int i = 1; i <= n; ++i) {
int u = id[i];
int A = a[u].first, B = a[u].second;
if (cb == A) {
answer += A;
cb = B;
} else if (cb > A) {
answer += A;
cb = cb - A + B;
} else {
answer += cb;
cb = B;
}
}
return answer;
}
int main() {
// freopen("b.in", "r", stdin);
// freopen("b.out", "w", stdout);
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
answer = 0;
for(int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
a[i] = get(s);
// scanf("%d%d", &a[i].first, &a[i].second);
}
iota(id + 1, id + n + 1, 1);
int ans = 0;
// sort(id + 1, id + n + 1, [&](int u, int v) {
// return a[u].first < a[v].first;
// });
// ans = max(ans, calc());
// sort(id + 1, id + n + 1, [&](int u, int v) {
// return a[u].second > a[v].second;
// });
// ans = max(ans, calc());
// sort(id + 1, id + n + 1, [&](int u, int v) {
// int p = a[u].second - a[u].first;
// int q = a[v].second - a[v].first;
// return p > q;
// });
// ans = max(ans, calc());
// sort(id + 1, id + n + 1, [&](int u, int v) {
// int p = a[u].second - a[u].first;
// int q = a[v].second - a[v].first;
// if (p >= 0 && q >= 0) {
// return a[u].first < a[v].first;
// } else if (p < 0 && q < 0) {
// return a[u].first > a[v].first;
// } else if (p >= 0 && q < 0) {
// return true;
// } else {
// return false;
// }
// });
sort(id + 1, id + n + 1, [&](int u, int v) {
int p = a[u].second - a[u].first;
int q = a[v].second - a[v].first;
if(p > 0) {
if(q > 0) {
return a[u].first < a[v].first;
}
else {
return true;
}
}
else if(p == 0) {
if(q > 0) {
return false;
}
else {
return true;
}
}
else {
if(q >= 0) {
return false;
}
else {
return a[u].second > a[v].second;
}
}
});
ans = max(ans, calc());
ans = answer + ans * 2;
printf("%d\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 202ms
memory: 4924kb
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