116262024-11-01 12:47:42MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Időlimit túllépés 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms512 KiB
2Elfogadva1ms320 KiB
3Elfogadva1ms320 KiB
subtask220/20
4Elfogadva1ms320 KiB
5Elfogadva1ms320 KiB
6Elfogadva1ms320 KiB
subtask330/30
7Elfogadva1ms508 KiB
8Elfogadva1ms320 KiB
9Elfogadva1ms320 KiB
10Elfogadva1ms388 KiB
11Elfogadva1ms508 KiB
subtask40/50
12Időlimit túllépés606ms83116 KiB
13Időlimit túllépés606ms83536 KiB
14Időlimit túllépés606ms81076 KiB
15Időlimit túllépés606ms80672 KiB
16Időlimit túllépés589ms82416 KiB
17Időlimit túllépés592ms80760 KiB
18Időlimit túllépés545ms64496 KiB
19Időlimit túllépés508ms68008 KiB
20Elfogadva488ms65520 KiB
21Időlimit túllépés518ms69460 KiB
22Időlimit túllépés583ms69872 KiB
23Időlimit túllépés586ms69492 KiB
24Elfogadva239ms26864 KiB
25Elfogadva193ms25584 KiB
26Elfogadva209ms28400 KiB
27Elfogadva216ms25944 KiB
28Elfogadva243ms27204 KiB
29Elfogadva234ms26352 KiB
30Elfogadva97ms11760 KiB
31Elfogadva79ms11248 KiB
32Elfogadva87ms11760 KiB
33Elfogadva90ms10412 KiB
34Elfogadva105ms12016 KiB
35Elfogadva83ms10512 KiB
36Elfogadva12ms1848 KiB
37Elfogadva4ms844 KiB
38Elfogadva12ms2104 KiB
39Elfogadva26ms3992 KiB
40Elfogadva37ms5688 KiB
41Elfogadva52ms7676 KiB
42Elfogadva48ms7112 KiB
43Elfogadva72ms10452 KiB
44Elfogadva163ms22000 KiB
45Elfogadva238ms32752 KiB
46Elfogadva349ms48160 KiB
47Elfogadva375ms51952 KiB
48Elfogadva476ms63216 KiB
49Időlimit túllépés527ms70896 KiB
50Időlimit túllépés555ms75760 KiB
51Elfogadva370ms52024 KiB
52Elfogadva135ms20280 KiB
53Elfogadva64ms10040 KiB
54Elfogadva78ms11832 KiB
55Időlimit túllépés606ms81648 KiB
56Időlimit túllépés595ms78832 KiB
57Időlimit túllépés574ms78900 KiB
58Időlimit túllépés605ms82968 KiB