QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #303902 | #236. Balanced Sequence | teraqqq | 100 ✓ | 26ms | 10548kb | C++23 | 1.3kb | 2024-01-13 05:52:44 | 2024-01-13 05:52:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
void solve() {
int n; cin >> n;
vector<string> v(n);
for (auto& w : v) cin >> w;
int sum_s = 0;
for (auto& w : v) sum_s += w.size();
int sum_h = 0;
vector<pi> delta;
for (auto& w : v) {
int h = 0, min_h = 0;
for (char c : w) {
h += (c == '(') - (c == ')');
min_h = min(min_h, h);
}
delta.emplace_back(h, min_h);
sum_h += h;
}
vector<pi> lft_part, rgt_part;
for (auto [h, p] : delta) {
if (h >= 0) {
lft_part.emplace_back(p, h);
} else {
rgt_part.emplace_back(p-h, -h);
}
}
sort(lft_part.rbegin(), lft_part.rend());
sort(rgt_part.rbegin(), rgt_part.rend());
int ans = sum_s;
vector<int> heights;
for (auto part : array{lft_part, rgt_part}) {
int h = 0;
for (auto [min_h, dh] : part) {
while (h + min_h < 0) ++h, --ans;
h += dh;
}
heights.push_back(h);
}
ans -= abs(heights[0] - heights[1]);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 26ms
memory: 10548kb
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