115962024-10-29 19:27:07DávidBob Baba Zárójelsorozatacpp17Accepted 100/100140ms6700 KiB
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

#define ll long long

int main() {
	int n;
	cin >> n;

	ll osszeg = 0;
	vector<int> szamok(n + 1);

	for(int i = 1; i <= n; i++) {
		cin >> szamok[i];
		osszeg += szamok[i];
	}

	vector<vector<bool>> dp(n + 1, vector<bool>(osszeg + 1));
	dp[0][0] = true;
	vector<vector<bool>> vissza(n + 1, vector<bool>(osszeg + 1));
	
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < osszeg; j++) {
			if(j - szamok[i] >= 0 && dp[i - 1][j - szamok[i]]) {
				dp[i][j] = true;
				vissza[i][j] = 0;
			}
			if(j + szamok[i] <= osszeg && dp[i - 1][j + szamok[i]]) {
				dp[i][j] = true;
				vissza[i][j] = 1;
			}
		}
	}

	if(!dp[n][0]) {
		cout << -1 << endl;
		return 0;
	}

	vector<char> eredmeny;
	int j = 0;
	for(int i = n; i > 0; i--) {
		if(!vissza[i][j]) {
			for(int k = 0; k < szamok[i]; k++) eredmeny.push_back('(');
			j -= szamok[i];
		} else {
			for(int k = 0; k < szamok[i]; k++) eredmeny.push_back(')');
			j += szamok[i];
		}
	}
	reverse(eredmeny.begin(), eredmeny.end());
	for(char i : eredmeny) {
		cout << i;
	}

	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms320 KiB
2Accepted1ms320 KiB
3Accepted1ms320 KiB
subtask220/20
4Accepted1ms320 KiB
5Accepted1ms320 KiB
6Accepted1ms508 KiB
subtask330/30
7Accepted1ms320 KiB
8Accepted1ms500 KiB
9Accepted1ms320 KiB
10Accepted1ms320 KiB
11Accepted1ms320 KiB
subtask450/50
12Accepted136ms6580 KiB
13Accepted136ms6584 KiB
14Accepted140ms6596 KiB
15Accepted138ms6700 KiB
16Accepted136ms6456 KiB
17Accepted136ms6580 KiB
18Accepted68ms3384 KiB
19Accepted71ms3508 KiB
20Accepted71ms3640 KiB
21Accepted70ms3640 KiB
22Accepted67ms3384 KiB
23Accepted68ms3384 KiB
24Accepted28ms1772 KiB
25Accepted28ms1648 KiB
26Accepted29ms1656 KiB
27Accepted28ms1644 KiB
28Accepted27ms1592 KiB
29Accepted27ms1592 KiB
30Accepted14ms1052 KiB
31Accepted14ms1080 KiB
32Accepted14ms1024 KiB
33Accepted14ms824 KiB
34Accepted14ms1020 KiB
35Accepted14ms824 KiB
36Accepted14ms1092 KiB
37Accepted8ms824 KiB
38Accepted14ms1080 KiB
39Accepted21ms1336 KiB
40Accepted27ms1404 KiB
41Accepted27ms1460 KiB
42Accepted28ms1592 KiB
43Accepted28ms1592 KiB
44Accepted37ms1928 KiB
45Accepted39ms2292 KiB
46Accepted52ms2872 KiB
47Accepted52ms2908 KiB
48Accepted54ms2908 KiB
49Accepted59ms3128 KiB
50Accepted65ms3440 KiB
51Accepted85ms4332 KiB
52Accepted89ms4920 KiB
53Accepted93ms5432 KiB
54Accepted109ms6072 KiB
55Accepted131ms6436 KiB
56Accepted109ms5316 KiB
57Accepted82ms4152 KiB
58Accepted86ms4408 KiB