11626 | 2024-11-01 12:47:42 | MagyarKendeSZLG | Bob Baba Zárójelsorozata | cpp17 | Time limit exceeded 50/100 | 606ms | 83536 KiB |
#include <cassert>
#include <iostream>
#include <numeric>
#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), ss(N + 1);
for (int& x : a) cin >> x;
partial_sum(a.rbegin(), a.rend(), ss.rbegin());
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] <= ss[i + 1]) {
ns.insert(x + a[i]);
pathS[i][x + a[i]] = x;
}
if (x - a[i] <= ss[i + 1] && 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 | 512 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 | 508 KiB | ||||
8 | Accepted | 1ms | 320 KiB | ||||
9 | Accepted | 1ms | 320 KiB | ||||
10 | Accepted | 1ms | 388 KiB | ||||
11 | Accepted | 1ms | 508 KiB | ||||
subtask4 | 0/50 | ||||||
12 | Time limit exceeded | 606ms | 83116 KiB | ||||
13 | Time limit exceeded | 606ms | 83536 KiB | ||||
14 | Time limit exceeded | 606ms | 81076 KiB | ||||
15 | Time limit exceeded | 606ms | 80672 KiB | ||||
16 | Time limit exceeded | 589ms | 82416 KiB | ||||
17 | Time limit exceeded | 592ms | 80760 KiB | ||||
18 | Time limit exceeded | 545ms | 64496 KiB | ||||
19 | Time limit exceeded | 508ms | 68008 KiB | ||||
20 | Accepted | 488ms | 65520 KiB | ||||
21 | Time limit exceeded | 518ms | 69460 KiB | ||||
22 | Time limit exceeded | 583ms | 69872 KiB | ||||
23 | Time limit exceeded | 586ms | 69492 KiB | ||||
24 | Accepted | 239ms | 26864 KiB | ||||
25 | Accepted | 193ms | 25584 KiB | ||||
26 | Accepted | 209ms | 28400 KiB | ||||
27 | Accepted | 216ms | 25944 KiB | ||||
28 | Accepted | 243ms | 27204 KiB | ||||
29 | Accepted | 234ms | 26352 KiB | ||||
30 | Accepted | 97ms | 11760 KiB | ||||
31 | Accepted | 79ms | 11248 KiB | ||||
32 | Accepted | 87ms | 11760 KiB | ||||
33 | Accepted | 90ms | 10412 KiB | ||||
34 | Accepted | 105ms | 12016 KiB | ||||
35 | Accepted | 83ms | 10512 KiB | ||||
36 | Accepted | 12ms | 1848 KiB | ||||
37 | Accepted | 4ms | 844 KiB | ||||
38 | Accepted | 12ms | 2104 KiB | ||||
39 | Accepted | 26ms | 3992 KiB | ||||
40 | Accepted | 37ms | 5688 KiB | ||||
41 | Accepted | 52ms | 7676 KiB | ||||
42 | Accepted | 48ms | 7112 KiB | ||||
43 | Accepted | 72ms | 10452 KiB | ||||
44 | Accepted | 163ms | 22000 KiB | ||||
45 | Accepted | 238ms | 32752 KiB | ||||
46 | Accepted | 349ms | 48160 KiB | ||||
47 | Accepted | 375ms | 51952 KiB | ||||
48 | Accepted | 476ms | 63216 KiB | ||||
49 | Time limit exceeded | 527ms | 70896 KiB | ||||
50 | Time limit exceeded | 555ms | 75760 KiB | ||||
51 | Accepted | 370ms | 52024 KiB | ||||
52 | Accepted | 135ms | 20280 KiB | ||||
53 | Accepted | 64ms | 10040 KiB | ||||
54 | Accepted | 78ms | 11832 KiB | ||||
55 | Time limit exceeded | 606ms | 81648 KiB | ||||
56 | Time limit exceeded | 595ms | 78832 KiB | ||||
57 | Time limit exceeded | 574ms | 78900 KiB | ||||
58 | Time limit exceeded | 605ms | 82968 KiB |