115742024-10-27 10:53:27chucknorrisBob Baba Zárójelsorozatacpp17Elfogadva 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;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms508 KiB
2Elfogadva1ms320 KiB
3Elfogadva1ms320 KiB
subtask220/20
4Elfogadva1ms320 KiB
5Elfogadva1ms320 KiB
6Elfogadva4ms548 KiB
subtask330/30
7Elfogadva2ms500 KiB
8Elfogadva1ms320 KiB
9Elfogadva2ms500 KiB
10Elfogadva1ms320 KiB
11Elfogadva1ms320 KiB
subtask450/50
12Elfogadva28ms14184 KiB
13Elfogadva150ms14584 KiB
14Elfogadva151ms15388 KiB
15Elfogadva149ms14972 KiB
16Elfogadva27ms13880 KiB
17Elfogadva28ms14656 KiB
18Elfogadva14ms7436 KiB
19Elfogadva136ms8272 KiB
20Elfogadva136ms8100 KiB
21Elfogadva136ms8244 KiB
22Elfogadva13ms6844 KiB
23Elfogadva14ms7224 KiB
24Elfogadva6ms3128 KiB
25Elfogadva125ms3912 KiB
26Elfogadva128ms4044 KiB
27Elfogadva8ms3472 KiB
28Elfogadva7ms2876 KiB
29Elfogadva6ms2876 KiB
30Elfogadva4ms1848 KiB
31Elfogadva123ms2284 KiB
32Elfogadva114ms2288 KiB
33Elfogadva4ms1768 KiB
34Elfogadva3ms1592 KiB
35Elfogadva3ms1592 KiB
36Elfogadva123ms2448 KiB
37Elfogadva123ms1832 KiB
38Elfogadva126ms2536 KiB
39Elfogadva127ms3640 KiB
40Elfogadva128ms4356 KiB
41Elfogadva128ms4420 KiB
42Elfogadva128ms4648 KiB
43Elfogadva128ms4400 KiB
44Elfogadva129ms5628 KiB
45Elfogadva128ms4888 KiB
46Elfogadva133ms6448 KiB
47Elfogadva131ms5968 KiB
48Elfogadva133ms6256 KiB
49Elfogadva130ms6240 KiB
50Elfogadva135ms6872 KiB
51Elfogadva138ms8900 KiB
52Elfogadva135ms6696 KiB
53Elfogadva134ms6256 KiB
54Elfogadva140ms8404 KiB
55Elfogadva150ms14156 KiB
56Elfogadva143ms12136 KiB
57Elfogadva136ms9096 KiB
58Elfogadva138ms9848 KiB