115952024-10-29 19:25:40DávidBob Baba Zárójelsorozatacpp17Hibás válasz 0/100170ms6712 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;
			}
		}
	}

	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
2Elfogadva1ms500 KiB
3Hibás válasz1ms532 KiB
subtask20/20
4Hibás válasz2ms320 KiB
5Hibás válasz2ms568 KiB
6Elfogadva1ms320 KiB
subtask30/30
7Elfogadva1ms508 KiB
8Elfogadva1ms320 KiB
9Elfogadva1ms320 KiB
10Hibás válasz1ms508 KiB
11Elfogadva1ms320 KiB
subtask40/50
12Hibás válasz168ms6588 KiB
13Elfogadva166ms6580 KiB
14Elfogadva168ms6712 KiB
15Elfogadva168ms6580 KiB
16Hibás válasz166ms6712 KiB
17Hibás válasz170ms6708 KiB
18Hibás válasz85ms3828 KiB
19Elfogadva86ms3640 KiB
20Elfogadva86ms3640 KiB
21Elfogadva86ms3500 KiB
22Hibás válasz82ms3384 KiB
23Hibás válasz85ms3572 KiB
24Hibás válasz35ms1592 KiB
25Elfogadva35ms1780 KiB
26Elfogadva35ms1592 KiB
27Hibás válasz35ms1592 KiB
28Hibás válasz34ms1624 KiB
29Hibás válasz34ms1656 KiB
30Hibás válasz17ms1028 KiB
31Elfogadva17ms1040 KiB
32Elfogadva17ms1024 KiB
33Hibás válasz17ms1032 KiB
34Hibás válasz17ms1016 KiB
35Hibás válasz18ms1032 KiB
36Elfogadva16ms912 KiB
37Elfogadva9ms824 KiB
38Elfogadva16ms1076 KiB
39Elfogadva25ms1216 KiB
40Elfogadva32ms1408 KiB
41Elfogadva32ms1592 KiB
42Elfogadva35ms1528 KiB
43Elfogadva32ms1484 KiB
44Elfogadva46ms1928 KiB
45Elfogadva46ms2108 KiB
46Elfogadva64ms2872 KiB
47Elfogadva64ms2872 KiB
48Elfogadva68ms2916 KiB
49Elfogadva71ms3180 KiB
50Elfogadva79ms3384 KiB
51Elfogadva104ms4328 KiB
52Elfogadva109ms4920 KiB
53Elfogadva115ms5284 KiB
54Elfogadva136ms6196 KiB
55Elfogadva162ms6352 KiB
56Elfogadva134ms5312 KiB
57Elfogadva100ms4108 KiB
58Elfogadva105ms4424 KiB