115962024-10-29 19:27:07DávidBob Baba Zárójelsorozatacpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms320 KiB
2Elfogadva1ms320 KiB
3Elfogadva1ms320 KiB
subtask220/20
4Elfogadva1ms320 KiB
5Elfogadva1ms320 KiB
6Elfogadva1ms508 KiB
subtask330/30
7Elfogadva1ms320 KiB
8Elfogadva1ms500 KiB
9Elfogadva1ms320 KiB
10Elfogadva1ms320 KiB
11Elfogadva1ms320 KiB
subtask450/50
12Elfogadva136ms6580 KiB
13Elfogadva136ms6584 KiB
14Elfogadva140ms6596 KiB
15Elfogadva138ms6700 KiB
16Elfogadva136ms6456 KiB
17Elfogadva136ms6580 KiB
18Elfogadva68ms3384 KiB
19Elfogadva71ms3508 KiB
20Elfogadva71ms3640 KiB
21Elfogadva70ms3640 KiB
22Elfogadva67ms3384 KiB
23Elfogadva68ms3384 KiB
24Elfogadva28ms1772 KiB
25Elfogadva28ms1648 KiB
26Elfogadva29ms1656 KiB
27Elfogadva28ms1644 KiB
28Elfogadva27ms1592 KiB
29Elfogadva27ms1592 KiB
30Elfogadva14ms1052 KiB
31Elfogadva14ms1080 KiB
32Elfogadva14ms1024 KiB
33Elfogadva14ms824 KiB
34Elfogadva14ms1020 KiB
35Elfogadva14ms824 KiB
36Elfogadva14ms1092 KiB
37Elfogadva8ms824 KiB
38Elfogadva14ms1080 KiB
39Elfogadva21ms1336 KiB
40Elfogadva27ms1404 KiB
41Elfogadva27ms1460 KiB
42Elfogadva28ms1592 KiB
43Elfogadva28ms1592 KiB
44Elfogadva37ms1928 KiB
45Elfogadva39ms2292 KiB
46Elfogadva52ms2872 KiB
47Elfogadva52ms2908 KiB
48Elfogadva54ms2908 KiB
49Elfogadva59ms3128 KiB
50Elfogadva65ms3440 KiB
51Elfogadva85ms4332 KiB
52Elfogadva89ms4920 KiB
53Elfogadva93ms5432 KiB
54Elfogadva109ms6072 KiB
55Elfogadva131ms6436 KiB
56Elfogadva109ms5316 KiB
57Elfogadva82ms4152 KiB
58Elfogadva86ms4408 KiB