11574 | 2024-10-27 10:53:27 | chucknorris | Bob Baba Zárójelsorozata | cpp17 | Accepted 100/100 | 151ms | 15388 KiB |
// NOTE: it is recommended to use this even if you don't understand the following code.
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define VMAX 50000
using namespace std;
bool dp[500][VMAX + 2];
int S = 0;
int main() {
// uncomment the two following lines if you want to read/write from files
// ifstream cin("input.txt");
// ofstream cout("output.txt");
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; ++i){
cin >> A[i]; S = S + A[i];
}
string ans = "";
if(N == 1) cout << "-1";
else if(N == 2){
if(A[0] == A[1]){
for(int i = 0; i < A[0]; i++) ans = ans + '(';
for(int i = 0; i < A[0]; i++) ans = ans + ')';
}
else ans = "-1";
cout << ans;
}
else{
///dp[i] = 1, ha nyitva van i zarojel
///A[i] - lehet nyito zarojel ==> hozzaadjuk az olyan zarojel sorozathoz ahol dp[j] = 1
///A[i] - lehet csuko zarojel ==> kivonjuk dp[j]=1-bol
dp[0][A[0]] = 1;///az elso zarojel csak nyito lehet
int M = A[0];
for(int i = 1; i < N; i++){
for(int j = M; j >= 0; j--){
if(dp[i - 1][j] == 1){
dp[i][j + A[i]] = 1; M = max(M, j + A[i]);
if(j - A[i] >= 0) dp[i][j - A[i]] = 1;
}
}
}
if(dp[N - 1][0] == 0) cout << "-1";
else{
int k = 0;
for(int i = N - 1; i > 0; i--){
if(dp[i - 1][k + A[i]] == 1){
///A[i] csuko
for(int j = 0; j < A[i]; j++) ans = ans + ')';
k = k + A[i];
}
else if(k >= A[i] and dp[i - 1][k - A[i]] == 1){
for(int j = 0; j < A[i]; j++) ans = ans + '(';
k = k - A[i];
}
}
for(int i = 0; i < A[0]; i++) ans = ans + '(';
for(int i = S - 1; i>= 0; --i) cout << ans[i];
}
}
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 1ms | 508 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 | 4ms | 548 KiB | ||||
subtask3 | 30/30 | ||||||
7 | Accepted | 2ms | 500 KiB | ||||
8 | Accepted | 1ms | 320 KiB | ||||
9 | Accepted | 2ms | 500 KiB | ||||
10 | Accepted | 1ms | 320 KiB | ||||
11 | Accepted | 1ms | 320 KiB | ||||
subtask4 | 50/50 | ||||||
12 | Accepted | 28ms | 14184 KiB | ||||
13 | Accepted | 150ms | 14584 KiB | ||||
14 | Accepted | 151ms | 15388 KiB | ||||
15 | Accepted | 149ms | 14972 KiB | ||||
16 | Accepted | 27ms | 13880 KiB | ||||
17 | Accepted | 28ms | 14656 KiB | ||||
18 | Accepted | 14ms | 7436 KiB | ||||
19 | Accepted | 136ms | 8272 KiB | ||||
20 | Accepted | 136ms | 8100 KiB | ||||
21 | Accepted | 136ms | 8244 KiB | ||||
22 | Accepted | 13ms | 6844 KiB | ||||
23 | Accepted | 14ms | 7224 KiB | ||||
24 | Accepted | 6ms | 3128 KiB | ||||
25 | Accepted | 125ms | 3912 KiB | ||||
26 | Accepted | 128ms | 4044 KiB | ||||
27 | Accepted | 8ms | 3472 KiB | ||||
28 | Accepted | 7ms | 2876 KiB | ||||
29 | Accepted | 6ms | 2876 KiB | ||||
30 | Accepted | 4ms | 1848 KiB | ||||
31 | Accepted | 123ms | 2284 KiB | ||||
32 | Accepted | 114ms | 2288 KiB | ||||
33 | Accepted | 4ms | 1768 KiB | ||||
34 | Accepted | 3ms | 1592 KiB | ||||
35 | Accepted | 3ms | 1592 KiB | ||||
36 | Accepted | 123ms | 2448 KiB | ||||
37 | Accepted | 123ms | 1832 KiB | ||||
38 | Accepted | 126ms | 2536 KiB | ||||
39 | Accepted | 127ms | 3640 KiB | ||||
40 | Accepted | 128ms | 4356 KiB | ||||
41 | Accepted | 128ms | 4420 KiB | ||||
42 | Accepted | 128ms | 4648 KiB | ||||
43 | Accepted | 128ms | 4400 KiB | ||||
44 | Accepted | 129ms | 5628 KiB | ||||
45 | Accepted | 128ms | 4888 KiB | ||||
46 | Accepted | 133ms | 6448 KiB | ||||
47 | Accepted | 131ms | 5968 KiB | ||||
48 | Accepted | 133ms | 6256 KiB | ||||
49 | Accepted | 130ms | 6240 KiB | ||||
50 | Accepted | 135ms | 6872 KiB | ||||
51 | Accepted | 138ms | 8900 KiB | ||||
52 | Accepted | 135ms | 6696 KiB | ||||
53 | Accepted | 134ms | 6256 KiB | ||||
54 | Accepted | 140ms | 8404 KiB | ||||
55 | Accepted | 150ms | 14156 KiB | ||||
56 | Accepted | 143ms | 12136 KiB | ||||
57 | Accepted | 136ms | 9096 KiB | ||||
58 | Accepted | 138ms | 9848 KiB |