116282024-11-01 13:11:41MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Accepted 100/100165ms3396 KiB
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

const int MAXM = 50005;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

    int N;
    cin >> N;
    vector<int> a(N);
    for (int& x : a) cin >> x;

    vector dp(N, vector<bool>(MAXM));
    dp[0][a[0]] = 1;

    for (int i = 1; i < N; i++) {
        for (int j = 0; j < MAXM; j++) {
            dp[i][j] =
                (j + a[i] < MAXM && dp[i - 1][j + a[i]]) ||
                (j - a[i] >= 0 && dp[i - 1][j - a[i]]);
        }
    }

    if (dp[N - 1][0]) {
        vector<int> result(N);
        for (int i = N - 1, x = 0; i > 0; i--) {
            if (x + a[i] < MAXM && dp[i - 1][x + a[i]]) {
                x += a[i];
                result[i] = 1;
            } else {
                x -= a[i];
            }
        }

        for (int i = 0; i < N; i++) {
            cout << string(a[i], "()"[result[i]]);
        }

        cout << "\n";
    } else {
        cout << "-1\n";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms320 KiB
2Accepted2ms320 KiB
3Accepted1ms320 KiB
subtask220/20
4Accepted1ms320 KiB
5Accepted1ms348 KiB
6Accepted1ms320 KiB
subtask330/30
7Accepted4ms320 KiB
8Accepted7ms320 KiB
9Accepted7ms556 KiB
10Accepted7ms552 KiB
11Accepted6ms320 KiB
subtask450/50
12Accepted163ms3384 KiB
13Accepted165ms3384 KiB
14Accepted165ms3384 KiB
15Accepted164ms3396 KiB
16Accepted165ms3384 KiB
17Accepted165ms3384 KiB
18Accepted82ms1972 KiB
19Accepted83ms1848 KiB
20Accepted82ms1848 KiB
21Accepted82ms1968 KiB
22Accepted82ms1848 KiB
23Accepted82ms1848 KiB
24Accepted34ms824 KiB
25Accepted34ms1080 KiB
26Accepted34ms1044 KiB
27Accepted34ms824 KiB
28Accepted34ms824 KiB
29Accepted34ms904 KiB
30Accepted17ms568 KiB
31Accepted17ms568 KiB
32Accepted17ms752 KiB
33Accepted17ms568 KiB
34Accepted17ms756 KiB
35Accepted17ms756 KiB
36Accepted14ms676 KiB
37Accepted9ms756 KiB
38Accepted14ms672 KiB
39Accepted23ms820 KiB
40Accepted28ms920 KiB
41Accepted28ms952 KiB
42Accepted30ms828 KiB
43Accepted29ms952 KiB
44Accepted41ms1172 KiB
45Accepted45ms1268 KiB
46Accepted61ms1592 KiB
47Accepted63ms1608 KiB
48Accepted65ms1592 KiB
49Accepted71ms1768 KiB
50Accepted79ms1940 KiB
51Accepted104ms2360 KiB
52Accepted119ms2684 KiB
53Accepted127ms2864 KiB
54Accepted146ms3188 KiB
55Accepted157ms3388 KiB
56Accepted130ms2884 KiB
57Accepted98ms2280 KiB
58Accepted104ms2372 KiB