11627 | 2024-11-01 12:51:54 | MagyarKendeSZLG | Bob Baba Zárójelsorozata | cpp17 | Időlimit túllépés 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";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 1ms | 320 KiB | ||||
2 | Elfogadva | 1ms | 320 KiB | ||||
3 | Elfogadva | 1ms | 320 KiB | ||||
subtask2 | 20/20 | ||||||
4 | Elfogadva | 1ms | 320 KiB | ||||
5 | Elfogadva | 1ms | 320 KiB | ||||
6 | Elfogadva | 1ms | 320 KiB | ||||
subtask3 | 30/30 | ||||||
7 | Elfogadva | 1ms | 320 KiB | ||||
8 | Elfogadva | 1ms | 320 KiB | ||||
9 | Elfogadva | 1ms | 320 KiB | ||||
10 | Elfogadva | 1ms | 320 KiB | ||||
11 | Elfogadva | 1ms | 320 KiB | ||||
subtask4 | 0/50 | ||||||
12 | Időlimit túllépés | 606ms | 83820 KiB | ||||
13 | Időlimit túllépés | 606ms | 81548 KiB | ||||
14 | Időlimit túllépés | 606ms | 81804 KiB | ||||
15 | Időlimit túllépés | 606ms | 82864 KiB | ||||
16 | Időlimit túllépés | 586ms | 82660 KiB | ||||
17 | Időlimit túllépés | 587ms | 78064 KiB | ||||
18 | Időlimit túllépés | 586ms | 73460 KiB | ||||
19 | Időlimit túllépés | 587ms | 73200 KiB | ||||
20 | Időlimit túllépés | 578ms | 74220 KiB | ||||
21 | Időlimit túllépés | 578ms | 76528 KiB | ||||
22 | Időlimit túllépés | 578ms | 77808 KiB | ||||
23 | Időlimit túllépés | 579ms | 74224 KiB | ||||
24 | Elfogadva | 495ms | 54360 KiB | ||||
25 | Elfogadva | 493ms | 58664 KiB | ||||
26 | Elfogadva | 488ms | 60248 KiB | ||||
27 | Időlimit túllépés | 583ms | 58436 KiB | ||||
28 | Elfogadva | 444ms | 50004 KiB | ||||
29 | Elfogadva | 493ms | 50384 KiB | ||||
30 | Elfogadva | 224ms | 26200 KiB | ||||
31 | Elfogadva | 207ms | 25944 KiB | ||||
32 | Elfogadva | 193ms | 25432 KiB | ||||
33 | Elfogadva | 284ms | 28248 KiB | ||||
34 | Elfogadva | 177ms | 21408 KiB | ||||
35 | Elfogadva | 207ms | 23848 KiB | ||||
36 | Elfogadva | 231ms | 26196 KiB | ||||
37 | Elfogadva | 86ms | 11864 KiB | ||||
38 | Elfogadva | 224ms | 27852 KiB | ||||
39 | Elfogadva | 428ms | 51288 KiB | ||||
40 | Időlimit túllépés | 592ms | 62728 KiB | ||||
41 | Időlimit túllépés | 605ms | 64856 KiB | ||||
42 | Időlimit túllépés | 587ms | 69464 KiB | ||||
43 | Időlimit túllépés | 580ms | 69976 KiB | ||||
44 | Időlimit túllépés | 584ms | 66052 KiB | ||||
45 | Időlimit túllépés | 606ms | 73304 KiB | ||||
46 | Időlimit túllépés | 591ms | 74992 KiB | ||||
47 | Időlimit túllépés | 583ms | 74484 KiB | ||||
48 | Időlimit túllépés | 592ms | 75504 KiB | ||||
49 | Időlimit túllépés | 605ms | 80360 KiB | ||||
50 | Időlimit túllépés | 583ms | 75504 KiB | ||||
51 | Időlimit túllépés | 591ms | 77156 KiB | ||||
52 | Időlimit túllépés | 570ms | 70128 KiB | ||||
53 | Elfogadva | 381ms | 50780 KiB | ||||
54 | Időlimit túllépés | 596ms | 75248 KiB | ||||
55 | Időlimit túllépés | 583ms | 81388 KiB | ||||
56 | Időlimit túllépés | 605ms | 81732 KiB | ||||
57 | Időlimit túllépés | 579ms | 75764 KiB | ||||
58 | Időlimit túllépés | 584ms | 76528 KiB |