oj.uz

Submission #708054

# Submission time Handle Problem Language Result Execution time Memory
708054 2023-03-11T01:05:49 Z DennisTran Bali Sculptures (APIO15_sculpture) C++17
46 / 100
 570 ms 262144 KB 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }

const int MAXN = 2005;

int N, L, R, a[MAXN];
long long sum[MAXN];

struct SUB1{
    long long ans = 1e18;
    vector <int> lim;

    void check(int sz) {
        sz--;
        if (sz < L || sz > R) return;
        sz++;
        long long tmp = 0;
        for (int i = 1; i < sz; i++) {
            tmp |= (sum[lim[i]] - sum[lim[i - 1]]);
        }
        ans = min(ans, tmp);
    }

    void Try(int id) {
        if (id == N + 1) {
            if (lim.back() != N) return;
            return void(check(lim.size()));
        }
        Try(id + 1);
        lim.emplace_back(id);
        Try(id + 1);
        lim.pop_back();
    }

    void solve(void) {
        lim.emplace_back(0);
        Try(1);
        cout << ans; exit(0);
    }
} sub1;

struct SUB2{
    unordered_set <long long> dp[MAXN][MAXN];
    void solve(void) {
        dp[0][0].insert(0);
        REP(i, N) {
            REP(j, min(i + 1, R)) {
                for (long long x : dp[i][j]) {
                    FOR(nxt, i + 1, N)
                        dp[nxt][j + 1].insert(x | sum[nxt] - sum[i]);
                }
            }
        }
        long long ans = 1e18;
        FOR(i, L, R)
            for (long long x : dp[N][i]) ans = min(ans, x);
        cout << ans;
    }
} sub2;

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    file("TASK");
    cin >> N >> L >> R;
    FOR(i, 1, N) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    if (N <= 20) sub1.solve();
    sub2.solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message

sculpture.cpp: In member function 'void SUB2::solve()':
sculpture.cpp:61:60: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   61 |                         dp[nxt][j + 1].insert(x | sum[nxt] - sum[i]);
      |                                                   ~~~~~~~~~^~~~~~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:9:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("TASK");
      |     ^~~~
sculpture.cpp:9:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:74:5: note: in expansion of macro 'file'
   74 |     file("TASK");
      |     ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 220592 KB Output is correct
2 Correct 125 ms 220520 KB Output is correct
3 Correct 126 ms 220492 KB Output is correct
4 Correct 116 ms 220564 KB Output is correct
5 Correct 117 ms 220592 KB Output is correct
6 Correct 118 ms 220568 KB Output is correct
7 Correct 119 ms 220492 KB Output is correct
8 Correct 122 ms 220492 KB Output is correct
9 Correct 120 ms 220596 KB Output is correct
10 Correct 120 ms 220644 KB Output is correct
11 Correct 123 ms 220616 KB Output is correct
12 Correct 126 ms 220496 KB Output is correct
13 Correct 128 ms 220496 KB Output is correct
14 Correct 121 ms 220640 KB Output is correct
15 Correct 120 ms 220564 KB Output is correct
16 Correct 120 ms 220544 KB Output is correct
17 Correct 122 ms 220592 KB Output is correct
18 Correct 119 ms 220520 KB Output is correct
19 Correct 116 ms 220556 KB Output is correct
20 Correct 117 ms 220592 KB Output is correct
21 Correct 130 ms 220540 KB Output is correct
22 Correct 121 ms 220492 KB Output is correct
23 Correct 122 ms 220560 KB Output is correct
24 Correct 122 ms 220472 KB Output is correct
25 Correct 126 ms 220556 KB Output is correct
26 Correct 127 ms 220592 KB Output is correct
27 Correct 122 ms 220508 KB Output is correct
28 Correct 120 ms 220624 KB Output is correct
29 Correct 124 ms 220696 KB Output is correct
30 Correct 119 ms 220672 KB Output is correct
31 Correct 137 ms 220564 KB Output is correct
32 Correct 126 ms 220472 KB Output is correct
33 Correct 128 ms 220464 KB Output is correct
34 Correct 130 ms 220592 KB Output is correct
35 Correct 125 ms 220588 KB Output is correct
36 Correct 128 ms 220592 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 220620 KB Output is correct
2 Correct 133 ms 220596 KB Output is correct
3 Correct 120 ms 220556 KB Output is correct
4 Correct 122 ms 220588 KB Output is correct
5 Correct 132 ms 220580 KB Output is correct
6 Correct 125 ms 220620 KB Output is correct
7 Correct 135 ms 220536 KB Output is correct
8 Correct 125 ms 220520 KB Output is correct
9 Correct 125 ms 220584 KB Output is correct
10 Correct 122 ms 220492 KB Output is correct
11 Correct 122 ms 220492 KB Output is correct
12 Correct 122 ms 220592 KB Output is correct
13 Correct 128 ms 220528 KB Output is correct
14 Correct 124 ms 220520 KB Output is correct
15 Correct 133 ms 220704 KB Output is correct
16 Correct 123 ms 220620 KB Output is correct
17 Correct 130 ms 220604 KB Output is correct
18 Correct 131 ms 220496 KB Output is correct
19 Correct 131 ms 220476 KB Output is correct
20 Correct 125 ms 220500 KB Output is correct
21 Correct 129 ms 220484 KB Output is correct
22 Correct 124 ms 220476 KB Output is correct
23 Correct 126 ms 220512 KB Output is correct
24 Correct 122 ms 220604 KB Output is correct
25 Correct 123 ms 220616 KB Output is correct
26 Correct 131 ms 220484 KB Output is correct
27 Correct 121 ms 220628 KB Output is correct
28 Correct 120 ms 220688 KB Output is correct
29 Correct 122 ms 220648 KB Output is correct
30 Correct 125 ms 221116 KB Output is correct
31 Correct 137 ms 221696 KB Output is correct
32 Correct 131 ms 221132 KB Output is correct
33 Correct 118 ms 220484 KB Output is correct
34 Correct 129 ms 221252 KB Output is correct
35 Correct 128 ms 221256 KB Output is correct
36 Correct 127 ms 221132 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 220492 KB Output is correct
2 Correct 119 ms 220572 KB Output is correct
3 Correct 121 ms 220500 KB Output is correct
4 Correct 132 ms 220588 KB Output is correct
5 Correct 129 ms 220560 KB Output is correct
6 Correct 123 ms 220544 KB Output is correct
7 Correct 123 ms 220484 KB Output is correct
8 Correct 134 ms 220520 KB Output is correct
9 Correct 126 ms 220504 KB Output is correct
10 Correct 124 ms 220488 KB Output is correct
11 Correct 125 ms 220492 KB Output is correct
12 Correct 124 ms 220692 KB Output is correct
13 Correct 130 ms 220592 KB Output is correct
14 Correct 123 ms 220572 KB Output is correct
15 Correct 119 ms 220696 KB Output is correct
16 Correct 120 ms 220604 KB Output is correct
17 Correct 124 ms 221012 KB Output is correct
18 Correct 126 ms 221672 KB Output is correct
19 Correct 123 ms 221132 KB Output is correct
20 Correct 120 ms 220512 KB Output is correct
21 Correct 124 ms 221312 KB Output is correct
22 Correct 137 ms 221196 KB Output is correct
23 Correct 124 ms 221012 KB Output is correct
24 Correct 133 ms 221776 KB Output is correct
25 Correct 140 ms 222020 KB Output is correct
26 Correct 183 ms 224764 KB Output is correct
27 Correct 193 ms 228028 KB Output is correct
28 Correct 223 ms 230524 KB Output is correct
29 Correct 181 ms 227404 KB Output is correct
30 Correct 124 ms 220532 KB Output is correct
31 Correct 249 ms 231560 KB Output is correct
32 Correct 247 ms 232304 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 220488 KB Output is correct
2 Correct 120 ms 220592 KB Output is correct
3 Correct 120 ms 220548 KB Output is correct
4 Correct 117 ms 220568 KB Output is correct
5 Correct 118 ms 220648 KB Output is correct
6 Correct 116 ms 220532 KB Output is correct
7 Correct 118 ms 220592 KB Output is correct
8 Correct 123 ms 220688 KB Output is correct
9 Correct 134 ms 220684 KB Output is correct
10 Correct 124 ms 220496 KB Output is correct
11 Correct 121 ms 220468 KB Output is correct
12 Correct 125 ms 220564 KB Output is correct
13 Correct 130 ms 220532 KB Output is correct
14 Correct 122 ms 220492 KB Output is correct
15 Correct 120 ms 220492 KB Output is correct
16 Correct 120 ms 220592 KB Output is correct
17 Correct 128 ms 220492 KB Output is correct
18 Correct 121 ms 220620 KB Output is correct
19 Correct 127 ms 220512 KB Output is correct
20 Correct 126 ms 220580 KB Output is correct
21 Correct 122 ms 220592 KB Output is correct
22 Correct 127 ms 220748 KB Output is correct
23 Correct 125 ms 220596 KB Output is correct
24 Correct 123 ms 220532 KB Output is correct
25 Correct 124 ms 220696 KB Output is correct
26 Correct 134 ms 220560 KB Output is correct
27 Correct 119 ms 220488 KB Output is correct
28 Correct 127 ms 220592 KB Output is correct
29 Correct 124 ms 220664 KB Output is correct
30 Correct 123 ms 220700 KB Output is correct
31 Correct 126 ms 220528 KB Output is correct
32 Correct 134 ms 220592 KB Output is correct
33 Correct 131 ms 220548 KB Output is correct
34 Correct 127 ms 220568 KB Output is correct
35 Correct 125 ms 220624 KB Output is correct
36 Correct 128 ms 220568 KB Output is correct
37 Correct 126 ms 220628 KB Output is correct
38 Correct 127 ms 220692 KB Output is correct
39 Correct 125 ms 220632 KB Output is correct
40 Correct 122 ms 221136 KB Output is correct
41 Correct 125 ms 221668 KB Output is correct
42 Correct 122 ms 221172 KB Output is correct
43 Correct 132 ms 220492 KB Output is correct
44 Correct 123 ms 221348 KB Output is correct
45 Correct 122 ms 221260 KB Output is correct
46 Correct 121 ms 221016 KB Output is correct
47 Correct 132 ms 221772 KB Output is correct
48 Correct 130 ms 221996 KB Output is correct
49 Correct 155 ms 224700 KB Output is correct
50 Correct 204 ms 228020 KB Output is correct
51 Correct 243 ms 230528 KB Output is correct
52 Correct 187 ms 227404 KB Output is correct
53 Correct 120 ms 220500 KB Output is correct
54 Correct 290 ms 231500 KB Output is correct
55 Correct 286 ms 232096 KB Output is correct
56 Correct 567 ms 252668 KB Output is correct
57 Runtime error 478 ms 262144 KB Execution killed with signal 9
58 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 220612 KB Output is correct
2 Correct 121 ms 220504 KB Output is correct
3 Correct 123 ms 220568 KB Output is correct
4 Correct 128 ms 220568 KB Output is correct
5 Correct 118 ms 220680 KB Output is correct
6 Correct 122 ms 220536 KB Output is correct
7 Correct 122 ms 220524 KB Output is correct
8 Correct 125 ms 220592 KB Output is correct
9 Correct 131 ms 220508 KB Output is correct
10 Correct 123 ms 220496 KB Output is correct
11 Correct 123 ms 220584 KB Output is correct
12 Correct 127 ms 220592 KB Output is correct
13 Correct 128 ms 220576 KB Output is correct
14 Correct 128 ms 220480 KB Output is correct
15 Correct 119 ms 220592 KB Output is correct
16 Correct 128 ms 220548 KB Output is correct
17 Correct 127 ms 220476 KB Output is correct
18 Correct 146 ms 220588 KB Output is correct
19 Correct 124 ms 220592 KB Output is correct
20 Correct 129 ms 220636 KB Output is correct
21 Correct 130 ms 220492 KB Output is correct
22 Correct 127 ms 220492 KB Output is correct
23 Correct 127 ms 220568 KB Output is correct
24 Correct 119 ms 220600 KB Output is correct
25 Correct 121 ms 220592 KB Output is correct
26 Correct 121 ms 220660 KB Output is correct
27 Correct 120 ms 221008 KB Output is correct
28 Correct 126 ms 221624 KB Output is correct
29 Correct 124 ms 221128 KB Output is correct
30 Correct 121 ms 220548 KB Output is correct
31 Correct 125 ms 221340 KB Output is correct
32 Correct 138 ms 221220 KB Output is correct
33 Correct 123 ms 221104 KB Output is correct
34 Correct 134 ms 221840 KB Output is correct
35 Correct 132 ms 221912 KB Output is correct
36 Correct 157 ms 224744 KB Output is correct
37 Correct 202 ms 228172 KB Output is correct
38 Correct 223 ms 230528 KB Output is correct
39 Correct 185 ms 227356 KB Output is correct
40 Correct 123 ms 220532 KB Output is correct
41 Correct 281 ms 231628 KB Output is correct
42 Correct 249 ms 232240 KB Output is correct
43 Correct 570 ms 252704 KB Output is correct
44 Runtime error 479 ms 262144 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -