| 11628 | 2024-11-01 13:11:41 | MagyarKendeSZLG | Bob Baba Zárójelsorozata | cpp17 | Elfogadva 100/100 | 165ms | 3396 KiB |
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int MAXM = 50005;
int main() {
cin.tie(0), ios::sync_with_stdio(0);
int N;
cin >> N;
vector<int> a(N);
for (int& x : a) cin >> x;
vector dp(N, vector<bool>(MAXM));
dp[0][a[0]] = 1;
for (int i = 1; i < N; i++) {
for (int j = 0; j < MAXM; j++) {
dp[i][j] =
(j + a[i] < MAXM && dp[i - 1][j + a[i]]) ||
(j - a[i] >= 0 && dp[i - 1][j - a[i]]);
}
}
if (dp[N - 1][0]) {
vector<int> result(N);
for (int i = N - 1, x = 0; i > 0; i--) {
if (x + a[i] < MAXM && dp[i - 1][x + a[i]]) {
x += a[i];
result[i] = 1;
} else {
x -= a[i];
}
}
for (int i = 0; i < N; i++) {
cout << string(a[i], "()"[result[i]]);
}
cout << "\n";
} else {
cout << "-1\n";
}
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 2ms | 320 KiB | ||||
| 2 | Elfogadva | 2ms | 320 KiB | ||||
| 3 | Elfogadva | 1ms | 320 KiB | ||||
| subtask2 | 20/20 | ||||||
| 4 | Elfogadva | 1ms | 320 KiB | ||||
| 5 | Elfogadva | 1ms | 348 KiB | ||||
| 6 | Elfogadva | 1ms | 320 KiB | ||||
| subtask3 | 30/30 | ||||||
| 7 | Elfogadva | 4ms | 320 KiB | ||||
| 8 | Elfogadva | 7ms | 320 KiB | ||||
| 9 | Elfogadva | 7ms | 556 KiB | ||||
| 10 | Elfogadva | 7ms | 552 KiB | ||||
| 11 | Elfogadva | 6ms | 320 KiB | ||||
| subtask4 | 50/50 | ||||||
| 12 | Elfogadva | 163ms | 3384 KiB | ||||
| 13 | Elfogadva | 165ms | 3384 KiB | ||||
| 14 | Elfogadva | 165ms | 3384 KiB | ||||
| 15 | Elfogadva | 164ms | 3396 KiB | ||||
| 16 | Elfogadva | 165ms | 3384 KiB | ||||
| 17 | Elfogadva | 165ms | 3384 KiB | ||||
| 18 | Elfogadva | 82ms | 1972 KiB | ||||
| 19 | Elfogadva | 83ms | 1848 KiB | ||||
| 20 | Elfogadva | 82ms | 1848 KiB | ||||
| 21 | Elfogadva | 82ms | 1968 KiB | ||||
| 22 | Elfogadva | 82ms | 1848 KiB | ||||
| 23 | Elfogadva | 82ms | 1848 KiB | ||||
| 24 | Elfogadva | 34ms | 824 KiB | ||||
| 25 | Elfogadva | 34ms | 1080 KiB | ||||
| 26 | Elfogadva | 34ms | 1044 KiB | ||||
| 27 | Elfogadva | 34ms | 824 KiB | ||||
| 28 | Elfogadva | 34ms | 824 KiB | ||||
| 29 | Elfogadva | 34ms | 904 KiB | ||||
| 30 | Elfogadva | 17ms | 568 KiB | ||||
| 31 | Elfogadva | 17ms | 568 KiB | ||||
| 32 | Elfogadva | 17ms | 752 KiB | ||||
| 33 | Elfogadva | 17ms | 568 KiB | ||||
| 34 | Elfogadva | 17ms | 756 KiB | ||||
| 35 | Elfogadva | 17ms | 756 KiB | ||||
| 36 | Elfogadva | 14ms | 676 KiB | ||||
| 37 | Elfogadva | 9ms | 756 KiB | ||||
| 38 | Elfogadva | 14ms | 672 KiB | ||||
| 39 | Elfogadva | 23ms | 820 KiB | ||||
| 40 | Elfogadva | 28ms | 920 KiB | ||||
| 41 | Elfogadva | 28ms | 952 KiB | ||||
| 42 | Elfogadva | 30ms | 828 KiB | ||||
| 43 | Elfogadva | 29ms | 952 KiB | ||||
| 44 | Elfogadva | 41ms | 1172 KiB | ||||
| 45 | Elfogadva | 45ms | 1268 KiB | ||||
| 46 | Elfogadva | 61ms | 1592 KiB | ||||
| 47 | Elfogadva | 63ms | 1608 KiB | ||||
| 48 | Elfogadva | 65ms | 1592 KiB | ||||
| 49 | Elfogadva | 71ms | 1768 KiB | ||||
| 50 | Elfogadva | 79ms | 1940 KiB | ||||
| 51 | Elfogadva | 104ms | 2360 KiB | ||||
| 52 | Elfogadva | 119ms | 2684 KiB | ||||
| 53 | Elfogadva | 127ms | 2864 KiB | ||||
| 54 | Elfogadva | 146ms | 3188 KiB | ||||
| 55 | Elfogadva | 157ms | 3388 KiB | ||||
| 56 | Elfogadva | 130ms | 2884 KiB | ||||
| 57 | Elfogadva | 98ms | 2280 KiB | ||||
| 58 | Elfogadva | 104ms | 2372 KiB | ||||