116252024-11-01 12:39:27MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Időlimit túllépés 50/100606ms84384 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;

    // for (int x : a) cout << x << " ";
    // cout << "\n\n";

    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) {
            ns.insert(x + a[i]);
            pathS[i][x + a[i]] = x;

            if (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
3Elfogadva1ms500 KiB
subtask220/20
4Elfogadva1ms320 KiB
5Elfogadva1ms320 KiB
6Elfogadva1ms320 KiB
subtask330/30
7Elfogadva1ms436 KiB
8Elfogadva1ms320 KiB
9Elfogadva1ms320 KiB
10Elfogadva1ms588 KiB
11Elfogadva1ms320 KiB
subtask40/50
12Időlimit túllépés606ms82416 KiB
13Időlimit túllépés606ms84384 KiB
14Időlimit túllépés606ms81848 KiB
15Időlimit túllépés606ms84224 KiB
16Időlimit túllépés578ms79684 KiB
17Időlimit túllépés583ms80848 KiB
18Időlimit túllépés578ms75952 KiB
19Időlimit túllépés584ms74064 KiB
20Időlimit túllépés588ms76884 KiB
21Időlimit túllépés588ms74244 KiB
22Időlimit túllépés588ms75504 KiB
23Időlimit túllépés588ms77816 KiB
24Időlimit túllépés504ms54364 KiB
25Elfogadva500ms58712 KiB
26Elfogadva488ms60248 KiB
27Időlimit túllépés588ms58456 KiB
28Elfogadva458ms50008 KiB
29Elfogadva458ms50264 KiB
30Elfogadva246ms26148 KiB
31Elfogadva204ms25936 KiB
32Elfogadva200ms25432 KiB
33Elfogadva275ms28248 KiB
34Elfogadva177ms21412 KiB
35Elfogadva225ms23680 KiB
36Elfogadva207ms26008 KiB
37Elfogadva89ms11864 KiB
38Elfogadva221ms27736 KiB
39Elfogadva483ms51440 KiB
40Időlimit túllépés592ms69448 KiB
41Időlimit túllépés603ms66120 KiB
42Időlimit túllépés587ms68184 KiB
43Időlimit túllépés588ms65492 KiB
44Időlimit túllépés587ms71536 KiB
45Időlimit túllépés606ms72280 KiB
46Időlimit túllépés582ms74220 KiB
47Időlimit túllépés588ms73968 KiB
48Időlimit túllépés584ms76208 KiB
49Időlimit túllépés605ms77984 KiB
50Időlimit túllépés587ms77712 KiB
51Időlimit túllépés596ms76528 KiB
52Időlimit túllépés560ms70096 KiB
53Elfogadva393ms50700 KiB
54Időlimit túllépés592ms76552 KiB
55Időlimit túllépés583ms79088 KiB
56Időlimit túllépés592ms77788 KiB
57Időlimit túllépés591ms78068 KiB
58Időlimit túllépés596ms76784 KiB