116272024-11-01 12:51:54MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Time limit exceeded 50/100606ms83820 KiB
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using ll = long long;

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

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

    unordered_set<int> s;
    s.insert(a[0]);

    vector<unordered_map<int, int>> pathS(N);
    pathS[0][a[0]] = 0;

    for (int i = 1; i < N; i++) {
        unordered_set<int> ns;
        for (int x : s) {
            if (x + a[i] <= 50005) {
                ns.insert(x + a[i]);
                pathS[i][x + a[i]] = x;
            }
            if (x - a[i] <= 50005 && x - a[i] >= 0) {
                ns.insert(x - a[i]);
                pathS[i][x - a[i]] = x;
            }
        }
        swap(s, ns);
    }

    // for (int i = 0; i < N; i++) {
    //     cout << i << ":\n";
    //     for (auto [k, v] : pathS[i]) {
    //         cout << k << " " << v << "\n";
    //     }
    //     cout << "\n";
    // }

    for (int x : s) {
        if (!x) {
            vector<int> result(N);
            for (int i = N - 1; i >= 0; i--) {
                result[i] = x - pathS[i][x];
                x = pathS[i][x];
            }

            for (int x : result) {
                cout << string(abs(x), "()"[x < 0]);
            }
            cout << "\n";

            exit(0);
        }
    }

    cout << "-1\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms320 KiB
2Accepted1ms320 KiB
3Accepted1ms320 KiB
subtask220/20
4Accepted1ms320 KiB
5Accepted1ms320 KiB
6Accepted1ms320 KiB
subtask330/30
7Accepted1ms320 KiB
8Accepted1ms320 KiB
9Accepted1ms320 KiB
10Accepted1ms320 KiB
11Accepted1ms320 KiB
subtask40/50
12Time limit exceeded606ms83820 KiB
13Time limit exceeded606ms81548 KiB
14Time limit exceeded606ms81804 KiB
15Time limit exceeded606ms82864 KiB
16Time limit exceeded586ms82660 KiB
17Time limit exceeded587ms78064 KiB
18Time limit exceeded586ms73460 KiB
19Time limit exceeded587ms73200 KiB
20Time limit exceeded578ms74220 KiB
21Time limit exceeded578ms76528 KiB
22Time limit exceeded578ms77808 KiB
23Time limit exceeded579ms74224 KiB
24Accepted495ms54360 KiB
25Accepted493ms58664 KiB
26Accepted488ms60248 KiB
27Time limit exceeded583ms58436 KiB
28Accepted444ms50004 KiB
29Accepted493ms50384 KiB
30Accepted224ms26200 KiB
31Accepted207ms25944 KiB
32Accepted193ms25432 KiB
33Accepted284ms28248 KiB
34Accepted177ms21408 KiB
35Accepted207ms23848 KiB
36Accepted231ms26196 KiB
37Accepted86ms11864 KiB
38Accepted224ms27852 KiB
39Accepted428ms51288 KiB
40Time limit exceeded592ms62728 KiB
41Time limit exceeded605ms64856 KiB
42Time limit exceeded587ms69464 KiB
43Time limit exceeded580ms69976 KiB
44Time limit exceeded584ms66052 KiB
45Time limit exceeded606ms73304 KiB
46Time limit exceeded591ms74992 KiB
47Time limit exceeded583ms74484 KiB
48Time limit exceeded592ms75504 KiB
49Time limit exceeded605ms80360 KiB
50Time limit exceeded583ms75504 KiB
51Time limit exceeded591ms77156 KiB
52Time limit exceeded570ms70128 KiB
53Accepted381ms50780 KiB
54Time limit exceeded596ms75248 KiB
55Time limit exceeded583ms81388 KiB
56Time limit exceeded605ms81732 KiB
57Time limit exceeded579ms75764 KiB
58Time limit exceeded584ms76528 KiB