| 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 | ||||