11627 | 2024-11-01 12:51:54 | MagyarKendeSZLG | Bob Baba Zárójelsorozata | cpp17 | Time limit exceeded 50/100 | 606ms | 83820 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;
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) {
if (x + a[i] <= 50005) {
ns.insert(x + a[i]);
pathS[i][x + a[i]] = x;
}
if (x - a[i] <= 50005 && 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 | 320 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 | 320 KiB | ||||
8 | Accepted | 1ms | 320 KiB | ||||
9 | Accepted | 1ms | 320 KiB | ||||
10 | Accepted | 1ms | 320 KiB | ||||
11 | Accepted | 1ms | 320 KiB | ||||
subtask4 | 0/50 | ||||||
12 | Time limit exceeded | 606ms | 83820 KiB | ||||
13 | Time limit exceeded | 606ms | 81548 KiB | ||||
14 | Time limit exceeded | 606ms | 81804 KiB | ||||
15 | Time limit exceeded | 606ms | 82864 KiB | ||||
16 | Time limit exceeded | 586ms | 82660 KiB | ||||
17 | Time limit exceeded | 587ms | 78064 KiB | ||||
18 | Time limit exceeded | 586ms | 73460 KiB | ||||
19 | Time limit exceeded | 587ms | 73200 KiB | ||||
20 | Time limit exceeded | 578ms | 74220 KiB | ||||
21 | Time limit exceeded | 578ms | 76528 KiB | ||||
22 | Time limit exceeded | 578ms | 77808 KiB | ||||
23 | Time limit exceeded | 579ms | 74224 KiB | ||||
24 | Accepted | 495ms | 54360 KiB | ||||
25 | Accepted | 493ms | 58664 KiB | ||||
26 | Accepted | 488ms | 60248 KiB | ||||
27 | Time limit exceeded | 583ms | 58436 KiB | ||||
28 | Accepted | 444ms | 50004 KiB | ||||
29 | Accepted | 493ms | 50384 KiB | ||||
30 | Accepted | 224ms | 26200 KiB | ||||
31 | Accepted | 207ms | 25944 KiB | ||||
32 | Accepted | 193ms | 25432 KiB | ||||
33 | Accepted | 284ms | 28248 KiB | ||||
34 | Accepted | 177ms | 21408 KiB | ||||
35 | Accepted | 207ms | 23848 KiB | ||||
36 | Accepted | 231ms | 26196 KiB | ||||
37 | Accepted | 86ms | 11864 KiB | ||||
38 | Accepted | 224ms | 27852 KiB | ||||
39 | Accepted | 428ms | 51288 KiB | ||||
40 | Time limit exceeded | 592ms | 62728 KiB | ||||
41 | Time limit exceeded | 605ms | 64856 KiB | ||||
42 | Time limit exceeded | 587ms | 69464 KiB | ||||
43 | Time limit exceeded | 580ms | 69976 KiB | ||||
44 | Time limit exceeded | 584ms | 66052 KiB | ||||
45 | Time limit exceeded | 606ms | 73304 KiB | ||||
46 | Time limit exceeded | 591ms | 74992 KiB | ||||
47 | Time limit exceeded | 583ms | 74484 KiB | ||||
48 | Time limit exceeded | 592ms | 75504 KiB | ||||
49 | Time limit exceeded | 605ms | 80360 KiB | ||||
50 | Time limit exceeded | 583ms | 75504 KiB | ||||
51 | Time limit exceeded | 591ms | 77156 KiB | ||||
52 | Time limit exceeded | 570ms | 70128 KiB | ||||
53 | Accepted | 381ms | 50780 KiB | ||||
54 | Time limit exceeded | 596ms | 75248 KiB | ||||
55 | Time limit exceeded | 583ms | 81388 KiB | ||||
56 | Time limit exceeded | 605ms | 81732 KiB | ||||
57 | Time limit exceeded | 579ms | 75764 KiB | ||||
58 | Time limit exceeded | 584ms | 76528 KiB |