115742024-10-27 10:53:27chucknorrisBob Baba Zárójelsorozatacpp17Accepted 100/100151ms15388 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;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Accepted1ms320 KiB
3Accepted1ms320 KiB
subtask220/20
4Accepted1ms320 KiB
5Accepted1ms320 KiB
6Accepted4ms548 KiB
subtask330/30
7Accepted2ms500 KiB
8Accepted1ms320 KiB
9Accepted2ms500 KiB
10Accepted1ms320 KiB
11Accepted1ms320 KiB
subtask450/50
12Accepted28ms14184 KiB
13Accepted150ms14584 KiB
14Accepted151ms15388 KiB
15Accepted149ms14972 KiB
16Accepted27ms13880 KiB
17Accepted28ms14656 KiB
18Accepted14ms7436 KiB
19Accepted136ms8272 KiB
20Accepted136ms8100 KiB
21Accepted136ms8244 KiB
22Accepted13ms6844 KiB
23Accepted14ms7224 KiB
24Accepted6ms3128 KiB
25Accepted125ms3912 KiB
26Accepted128ms4044 KiB
27Accepted8ms3472 KiB
28Accepted7ms2876 KiB
29Accepted6ms2876 KiB
30Accepted4ms1848 KiB
31Accepted123ms2284 KiB
32Accepted114ms2288 KiB
33Accepted4ms1768 KiB
34Accepted3ms1592 KiB
35Accepted3ms1592 KiB
36Accepted123ms2448 KiB
37Accepted123ms1832 KiB
38Accepted126ms2536 KiB
39Accepted127ms3640 KiB
40Accepted128ms4356 KiB
41Accepted128ms4420 KiB
42Accepted128ms4648 KiB
43Accepted128ms4400 KiB
44Accepted129ms5628 KiB
45Accepted128ms4888 KiB
46Accepted133ms6448 KiB
47Accepted131ms5968 KiB
48Accepted133ms6256 KiB
49Accepted130ms6240 KiB
50Accepted135ms6872 KiB
51Accepted138ms8900 KiB
52Accepted135ms6696 KiB
53Accepted134ms6256 KiB
54Accepted140ms8404 KiB
55Accepted150ms14156 KiB
56Accepted143ms12136 KiB
57Accepted136ms9096 KiB
58Accepted138ms9848 KiB