116262024-11-01 12:47:42MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Time limit exceeded 50/100606ms83536 KiB
#include <cassert>
#include <iostream>
#include <numeric>
#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), ss(N + 1);
    for (int& x : a) cin >> x;

    partial_sum(a.rbegin(), a.rend(), ss.rbegin());

    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] <= ss[i + 1]) {
                ns.insert(x + a[i]);
                pathS[i][x + a[i]] = x;
            }
            if (x - a[i] <= ss[i + 1] && 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
1Accepted1ms512 KiB
2Accepted1ms320 KiB
3Accepted1ms320 KiB
subtask220/20
4Accepted1ms320 KiB
5Accepted1ms320 KiB
6Accepted1ms320 KiB
subtask330/30
7Accepted1ms508 KiB
8Accepted1ms320 KiB
9Accepted1ms320 KiB
10Accepted1ms388 KiB
11Accepted1ms508 KiB
subtask40/50
12Time limit exceeded606ms83116 KiB
13Time limit exceeded606ms83536 KiB
14Time limit exceeded606ms81076 KiB
15Time limit exceeded606ms80672 KiB
16Time limit exceeded589ms82416 KiB
17Time limit exceeded592ms80760 KiB
18Time limit exceeded545ms64496 KiB
19Time limit exceeded508ms68008 KiB
20Accepted488ms65520 KiB
21Time limit exceeded518ms69460 KiB
22Time limit exceeded583ms69872 KiB
23Time limit exceeded586ms69492 KiB
24Accepted239ms26864 KiB
25Accepted193ms25584 KiB
26Accepted209ms28400 KiB
27Accepted216ms25944 KiB
28Accepted243ms27204 KiB
29Accepted234ms26352 KiB
30Accepted97ms11760 KiB
31Accepted79ms11248 KiB
32Accepted87ms11760 KiB
33Accepted90ms10412 KiB
34Accepted105ms12016 KiB
35Accepted83ms10512 KiB
36Accepted12ms1848 KiB
37Accepted4ms844 KiB
38Accepted12ms2104 KiB
39Accepted26ms3992 KiB
40Accepted37ms5688 KiB
41Accepted52ms7676 KiB
42Accepted48ms7112 KiB
43Accepted72ms10452 KiB
44Accepted163ms22000 KiB
45Accepted238ms32752 KiB
46Accepted349ms48160 KiB
47Accepted375ms51952 KiB
48Accepted476ms63216 KiB
49Time limit exceeded527ms70896 KiB
50Time limit exceeded555ms75760 KiB
51Accepted370ms52024 KiB
52Accepted135ms20280 KiB
53Accepted64ms10040 KiB
54Accepted78ms11832 KiB
55Time limit exceeded606ms81648 KiB
56Time limit exceeded595ms78832 KiB
57Time limit exceeded574ms78900 KiB
58Time limit exceeded605ms82968 KiB