116272024-11-01 12:51:54MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Időlimit túllépés 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms320 KiB
2Elfogadva1ms320 KiB
3Elfogadva1ms320 KiB
subtask220/20
4Elfogadva1ms320 KiB
5Elfogadva1ms320 KiB
6Elfogadva1ms320 KiB
subtask330/30
7Elfogadva1ms320 KiB
8Elfogadva1ms320 KiB
9Elfogadva1ms320 KiB
10Elfogadva1ms320 KiB
11Elfogadva1ms320 KiB
subtask40/50
12Időlimit túllépés606ms83820 KiB
13Időlimit túllépés606ms81548 KiB
14Időlimit túllépés606ms81804 KiB
15Időlimit túllépés606ms82864 KiB
16Időlimit túllépés586ms82660 KiB
17Időlimit túllépés587ms78064 KiB
18Időlimit túllépés586ms73460 KiB
19Időlimit túllépés587ms73200 KiB
20Időlimit túllépés578ms74220 KiB
21Időlimit túllépés578ms76528 KiB
22Időlimit túllépés578ms77808 KiB
23Időlimit túllépés579ms74224 KiB
24Elfogadva495ms54360 KiB
25Elfogadva493ms58664 KiB
26Elfogadva488ms60248 KiB
27Időlimit túllépés583ms58436 KiB
28Elfogadva444ms50004 KiB
29Elfogadva493ms50384 KiB
30Elfogadva224ms26200 KiB
31Elfogadva207ms25944 KiB
32Elfogadva193ms25432 KiB
33Elfogadva284ms28248 KiB
34Elfogadva177ms21408 KiB
35Elfogadva207ms23848 KiB
36Elfogadva231ms26196 KiB
37Elfogadva86ms11864 KiB
38Elfogadva224ms27852 KiB
39Elfogadva428ms51288 KiB
40Időlimit túllépés592ms62728 KiB
41Időlimit túllépés605ms64856 KiB
42Időlimit túllépés587ms69464 KiB
43Időlimit túllépés580ms69976 KiB
44Időlimit túllépés584ms66052 KiB
45Időlimit túllépés606ms73304 KiB
46Időlimit túllépés591ms74992 KiB
47Időlimit túllépés583ms74484 KiB
48Időlimit túllépés592ms75504 KiB
49Időlimit túllépés605ms80360 KiB
50Időlimit túllépés583ms75504 KiB
51Időlimit túllépés591ms77156 KiB
52Időlimit túllépés570ms70128 KiB
53Elfogadva381ms50780 KiB
54Időlimit túllépés596ms75248 KiB
55Időlimit túllépés583ms81388 KiB
56Időlimit túllépés605ms81732 KiB
57Időlimit túllépés579ms75764 KiB
58Időlimit túllépés584ms76528 KiB