11574 | 2024-10-27 10:53:27 | chucknorris | Bob Baba Zárójelsorozata | cpp17 | Elfogadva 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 1ms | 508 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 | 4ms | 548 KiB | ||||
subtask3 | 30/30 | ||||||
7 | Elfogadva | 2ms | 500 KiB | ||||
8 | Elfogadva | 1ms | 320 KiB | ||||
9 | Elfogadva | 2ms | 500 KiB | ||||
10 | Elfogadva | 1ms | 320 KiB | ||||
11 | Elfogadva | 1ms | 320 KiB | ||||
subtask4 | 50/50 | ||||||
12 | Elfogadva | 28ms | 14184 KiB | ||||
13 | Elfogadva | 150ms | 14584 KiB | ||||
14 | Elfogadva | 151ms | 15388 KiB | ||||
15 | Elfogadva | 149ms | 14972 KiB | ||||
16 | Elfogadva | 27ms | 13880 KiB | ||||
17 | Elfogadva | 28ms | 14656 KiB | ||||
18 | Elfogadva | 14ms | 7436 KiB | ||||
19 | Elfogadva | 136ms | 8272 KiB | ||||
20 | Elfogadva | 136ms | 8100 KiB | ||||
21 | Elfogadva | 136ms | 8244 KiB | ||||
22 | Elfogadva | 13ms | 6844 KiB | ||||
23 | Elfogadva | 14ms | 7224 KiB | ||||
24 | Elfogadva | 6ms | 3128 KiB | ||||
25 | Elfogadva | 125ms | 3912 KiB | ||||
26 | Elfogadva | 128ms | 4044 KiB | ||||
27 | Elfogadva | 8ms | 3472 KiB | ||||
28 | Elfogadva | 7ms | 2876 KiB | ||||
29 | Elfogadva | 6ms | 2876 KiB | ||||
30 | Elfogadva | 4ms | 1848 KiB | ||||
31 | Elfogadva | 123ms | 2284 KiB | ||||
32 | Elfogadva | 114ms | 2288 KiB | ||||
33 | Elfogadva | 4ms | 1768 KiB | ||||
34 | Elfogadva | 3ms | 1592 KiB | ||||
35 | Elfogadva | 3ms | 1592 KiB | ||||
36 | Elfogadva | 123ms | 2448 KiB | ||||
37 | Elfogadva | 123ms | 1832 KiB | ||||
38 | Elfogadva | 126ms | 2536 KiB | ||||
39 | Elfogadva | 127ms | 3640 KiB | ||||
40 | Elfogadva | 128ms | 4356 KiB | ||||
41 | Elfogadva | 128ms | 4420 KiB | ||||
42 | Elfogadva | 128ms | 4648 KiB | ||||
43 | Elfogadva | 128ms | 4400 KiB | ||||
44 | Elfogadva | 129ms | 5628 KiB | ||||
45 | Elfogadva | 128ms | 4888 KiB | ||||
46 | Elfogadva | 133ms | 6448 KiB | ||||
47 | Elfogadva | 131ms | 5968 KiB | ||||
48 | Elfogadva | 133ms | 6256 KiB | ||||
49 | Elfogadva | 130ms | 6240 KiB | ||||
50 | Elfogadva | 135ms | 6872 KiB | ||||
51 | Elfogadva | 138ms | 8900 KiB | ||||
52 | Elfogadva | 135ms | 6696 KiB | ||||
53 | Elfogadva | 134ms | 6256 KiB | ||||
54 | Elfogadva | 140ms | 8404 KiB | ||||
55 | Elfogadva | 150ms | 14156 KiB | ||||
56 | Elfogadva | 143ms | 12136 KiB | ||||
57 | Elfogadva | 136ms | 9096 KiB | ||||
58 | Elfogadva | 138ms | 9848 KiB |