11625 | 2024-11-01 12:39:27 | MagyarKendeSZLG | Bob Baba Zárójelsorozata | cpp17 | Time limit exceeded 50/100 | 606ms | 84384 KiB |
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
int main() {
cin.tie(0), ios::sync_with_stdio(0);
int N;
cin >> N;
vector<int> a(N);
for (int& x : a) cin >> x;
// for (int x : a) cout << x << " ";
// cout << "\n\n";
unordered_set<int> s;
s.insert(a[0]);
vector<unordered_map<int, int>> pathS(N);
pathS[0][a[0]] = 0;
for (int i = 1; i < N; i++) {
unordered_set<int> ns;
for (int x : s) {
ns.insert(x + a[i]);
pathS[i][x + a[i]] = x;
if (x - a[i] >= 0) {
ns.insert(x - a[i]);
pathS[i][x - a[i]] = x;
}
}
swap(s, ns);
}
// for (int i = 0; i < N; i++) {
// cout << i << ":\n";
// for (auto [k, v] : pathS[i]) {
// cout << k << " " << v << "\n";
// }
// cout << "\n";
// }
for (int x : s) {
if (!x) {
vector<int> result(N);
for (int i = N - 1; i >= 0; i--) {
result[i] = x - pathS[i][x];
x = pathS[i][x];
}
for (int x : result) {
cout << string(abs(x), "()"[x < 0]);
}
cout << "\n";
exit(0);
}
}
cout << "-1\n";
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 1ms | 320 KiB | ||||
2 | Accepted | 1ms | 320 KiB | ||||
3 | Accepted | 1ms | 500 KiB | ||||
subtask2 | 20/20 | ||||||
4 | Accepted | 1ms | 320 KiB | ||||
5 | Accepted | 1ms | 320 KiB | ||||
6 | Accepted | 1ms | 320 KiB | ||||
subtask3 | 30/30 | ||||||
7 | Accepted | 1ms | 436 KiB | ||||
8 | Accepted | 1ms | 320 KiB | ||||
9 | Accepted | 1ms | 320 KiB | ||||
10 | Accepted | 1ms | 588 KiB | ||||
11 | Accepted | 1ms | 320 KiB | ||||
subtask4 | 0/50 | ||||||
12 | Time limit exceeded | 606ms | 82416 KiB | ||||
13 | Time limit exceeded | 606ms | 84384 KiB | ||||
14 | Time limit exceeded | 606ms | 81848 KiB | ||||
15 | Time limit exceeded | 606ms | 84224 KiB | ||||
16 | Time limit exceeded | 578ms | 79684 KiB | ||||
17 | Time limit exceeded | 583ms | 80848 KiB | ||||
18 | Time limit exceeded | 578ms | 75952 KiB | ||||
19 | Time limit exceeded | 584ms | 74064 KiB | ||||
20 | Time limit exceeded | 588ms | 76884 KiB | ||||
21 | Time limit exceeded | 588ms | 74244 KiB | ||||
22 | Time limit exceeded | 588ms | 75504 KiB | ||||
23 | Time limit exceeded | 588ms | 77816 KiB | ||||
24 | Time limit exceeded | 504ms | 54364 KiB | ||||
25 | Accepted | 500ms | 58712 KiB | ||||
26 | Accepted | 488ms | 60248 KiB | ||||
27 | Time limit exceeded | 588ms | 58456 KiB | ||||
28 | Accepted | 458ms | 50008 KiB | ||||
29 | Accepted | 458ms | 50264 KiB | ||||
30 | Accepted | 246ms | 26148 KiB | ||||
31 | Accepted | 204ms | 25936 KiB | ||||
32 | Accepted | 200ms | 25432 KiB | ||||
33 | Accepted | 275ms | 28248 KiB | ||||
34 | Accepted | 177ms | 21412 KiB | ||||
35 | Accepted | 225ms | 23680 KiB | ||||
36 | Accepted | 207ms | 26008 KiB | ||||
37 | Accepted | 89ms | 11864 KiB | ||||
38 | Accepted | 221ms | 27736 KiB | ||||
39 | Accepted | 483ms | 51440 KiB | ||||
40 | Time limit exceeded | 592ms | 69448 KiB | ||||
41 | Time limit exceeded | 603ms | 66120 KiB | ||||
42 | Time limit exceeded | 587ms | 68184 KiB | ||||
43 | Time limit exceeded | 588ms | 65492 KiB | ||||
44 | Time limit exceeded | 587ms | 71536 KiB | ||||
45 | Time limit exceeded | 606ms | 72280 KiB | ||||
46 | Time limit exceeded | 582ms | 74220 KiB | ||||
47 | Time limit exceeded | 588ms | 73968 KiB | ||||
48 | Time limit exceeded | 584ms | 76208 KiB | ||||
49 | Time limit exceeded | 605ms | 77984 KiB | ||||
50 | Time limit exceeded | 587ms | 77712 KiB | ||||
51 | Time limit exceeded | 596ms | 76528 KiB | ||||
52 | Time limit exceeded | 560ms | 70096 KiB | ||||
53 | Accepted | 393ms | 50700 KiB | ||||
54 | Time limit exceeded | 592ms | 76552 KiB | ||||
55 | Time limit exceeded | 583ms | 79088 KiB | ||||
56 | Time limit exceeded | 592ms | 77788 KiB | ||||
57 | Time limit exceeded | 591ms | 78068 KiB | ||||
58 | Time limit exceeded | 596ms | 76784 KiB |