oj.uz

Submission #743424

# Submission time Handle Problem Language Result Execution time Memory
743424 2023-05-17T11:33:18 Z Magikarp4000 Bali Sculptures (APIO15_sculpture) C++17
46 / 100
 1000 ms 3224 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#define int long long

const int MAXN = 1e2+1, LOG = 41;
int n,A,B;
int a[MAXN], p[MAXN];
int dp[MAXN][MAXN], res[LOG];
vector<int> v[MAXN][MAXN];

signed main() {
    cin >> n >> A >> B;
    FOR(i,0,n) cin >> a[i];
    FOR(i,1,n+1) p[i] = p[i-1]+a[i-1];
    dp[0][0] = 1;
    FOR(i,0,n) {
        FOR(j,i,n) {
            int x = p[j+1]-p[i];
            while (x > 0) {
                v[i][j].PB(x%2);
                x /= 2;
            }
            int vn = v[i][j].size();
            FOR(k,0,LOG-vn) v[i][j].PB(0);
        }
    }
    FORR(k,LOG-1,-1) {
        FOR(i,0,n+1) {
            FOR(j,1,n+1) dp[i][j] = 0;
        }
        FOR(j,0,n) {
            FOR(i,0,n+1) {
                FOR(l,i+1,n+1) {
                    bool ok = 1;
                    FORR(k1,LOG-1,k) if (v[i][l-1][k1] && !res[k1]) ok = 0;
                    dp[l][j+1] = dp[l][j+1] || (dp[i][j] && ok && !v[i][l-1][k]);
                }
            }
        }
        res[k] = 1;
        FOR(x,A,B+1) {
            if (dp[n][x]) res[k] = 0;
        }
    }
    int ans = 0, cur = 1;
    FOR(k,0,LOG+1) {
        ans += cur*res[k];
        cur *= 2;
    }
    cout << ans;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:68:25: warning: iteration 41 invokes undefined behavior [-Waggressive-loop-optimizations]
   68 |         ans += cur*res[k];
      |                    ~~~~~^
sculpture.cpp:10:38: note: within this loop
   10 | #define FOR(i,s,n) for (int i = s; i < n; i++)
......
   67 |     FOR(k,0,LOG+1) {
      |         ~~~~~~~~~                     
sculpture.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(k,0,LOG+1) {
      |     ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 540 KB Output is correct
5 Correct 1 ms 544 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 4 ms 644 KB Output is correct
8 Correct 5 ms 672 KB Output is correct
9 Correct 5 ms 668 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 6 ms 672 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 544 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 5 ms 596 KB Output is correct
22 Correct 8 ms 672 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 5 ms 596 KB Output is correct
25 Correct 5 ms 596 KB Output is correct
26 Correct 5 ms 672 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 4 ms 596 KB Output is correct
30 Correct 10 ms 660 KB Output is correct
31 Correct 8 ms 596 KB Output is correct
32 Correct 6 ms 596 KB Output is correct
33 Correct 7 ms 608 KB Output is correct
34 Correct 8 ms 668 KB Output is correct
35 Correct 8 ms 676 KB Output is correct
36 Correct 7 ms 676 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 4 ms 544 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 5 ms 676 KB Output is correct
9 Correct 5 ms 672 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 6 ms 676 KB Output is correct
12 Correct 6 ms 672 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 7 ms 596 KB Output is correct
23 Correct 6 ms 596 KB Output is correct
24 Correct 5 ms 676 KB Output is correct
25 Correct 6 ms 596 KB Output is correct
26 Correct 5 ms 596 KB Output is correct
27 Correct 6 ms 680 KB Output is correct
28 Correct 15 ms 680 KB Output is correct
29 Correct 48 ms 944 KB Output is correct
30 Correct 44 ms 1028 KB Output is correct
31 Correct 76 ms 1236 KB Output is correct
32 Correct 77 ms 1236 KB Output is correct
33 Correct 79 ms 1220 KB Output is correct
34 Correct 99 ms 1236 KB Output is correct
35 Correct 97 ms 1236 KB Output is correct
36 Correct 89 ms 1236 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 5 ms 676 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 5 ms 672 KB Output is correct
14 Correct 6 ms 596 KB Output is correct
15 Correct 10 ms 676 KB Output is correct
16 Correct 45 ms 940 KB Output is correct
17 Correct 77 ms 1024 KB Output is correct
18 Correct 87 ms 1236 KB Output is correct
19 Correct 101 ms 1228 KB Output is correct
20 Correct 105 ms 1236 KB Output is correct
21 Correct 100 ms 1224 KB Output is correct
22 Correct 85 ms 1236 KB Output is correct
23 Correct 84 ms 1188 KB Output is correct
24 Correct 102 ms 1252 KB Output is correct
25 Correct 203 ms 1704 KB Output is correct
26 Correct 374 ms 2180 KB Output is correct
27 Correct 594 ms 2772 KB Output is correct
28 Correct 746 ms 3212 KB Output is correct
29 Correct 802 ms 3208 KB Output is correct
30 Correct 742 ms 3216 KB Output is correct
31 Correct 728 ms 3216 KB Output is correct
32 Correct 776 ms 3212 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 548 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 7 ms 676 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 8 ms 672 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 1 ms 544 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 6 ms 680 KB Output is correct
22 Correct 6 ms 676 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 6 ms 668 KB Output is correct
25 Correct 8 ms 596 KB Output is correct
26 Correct 5 ms 672 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 5 ms 596 KB Output is correct
30 Correct 13 ms 668 KB Output is correct
31 Correct 6 ms 596 KB Output is correct
32 Correct 8 ms 684 KB Output is correct
33 Correct 10 ms 596 KB Output is correct
34 Correct 8 ms 596 KB Output is correct
35 Correct 9 ms 544 KB Output is correct
36 Correct 11 ms 596 KB Output is correct
37 Correct 6 ms 596 KB Output is correct
38 Correct 12 ms 736 KB Output is correct
39 Correct 36 ms 852 KB Output is correct
40 Correct 51 ms 1032 KB Output is correct
41 Correct 74 ms 1236 KB Output is correct
42 Correct 91 ms 1236 KB Output is correct
43 Correct 85 ms 1228 KB Output is correct
44 Correct 74 ms 1236 KB Output is correct
45 Correct 71 ms 1236 KB Output is correct
46 Correct 75 ms 1216 KB Output is correct
47 Correct 89 ms 1252 KB Output is correct
48 Correct 203 ms 1692 KB Output is correct
49 Correct 338 ms 2176 KB Output is correct
50 Correct 450 ms 2832 KB Output is correct
51 Correct 647 ms 3212 KB Output is correct
52 Correct 714 ms 3220 KB Output is correct
53 Correct 735 ms 3212 KB Output is correct
54 Correct 654 ms 3156 KB Output is correct
55 Correct 632 ms 3212 KB Output is correct
56 Correct 225 ms 1252 KB Output is correct
57 Correct 840 ms 2180 KB Output is correct
58 Execution timed out 1075 ms 2772 KB Time limit exceeded
59 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 552 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 5 ms 672 KB Output is correct
10 Correct 7 ms 676 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 5 ms 672 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 11 ms 664 KB Output is correct
18 Correct 6 ms 596 KB Output is correct
19 Correct 7 ms 680 KB Output is correct
20 Correct 8 ms 596 KB Output is correct
21 Correct 8 ms 596 KB Output is correct
22 Correct 7 ms 596 KB Output is correct
23 Correct 7 ms 596 KB Output is correct
24 Correct 6 ms 596 KB Output is correct
25 Correct 10 ms 852 KB Output is correct
26 Correct 32 ms 936 KB Output is correct
27 Correct 40 ms 980 KB Output is correct
28 Correct 87 ms 1236 KB Output is correct
29 Correct 82 ms 1236 KB Output is correct
30 Correct 88 ms 1236 KB Output is correct
31 Correct 79 ms 1236 KB Output is correct
32 Correct 81 ms 1236 KB Output is correct
33 Correct 75 ms 1236 KB Output is correct
34 Correct 93 ms 1252 KB Output is correct
35 Correct 189 ms 1700 KB Output is correct
36 Correct 294 ms 2132 KB Output is correct
37 Correct 508 ms 2772 KB Output is correct
38 Correct 625 ms 3216 KB Output is correct
39 Correct 677 ms 3208 KB Output is correct
40 Correct 654 ms 3224 KB Output is correct
41 Correct 610 ms 3216 KB Output is correct
42 Correct 599 ms 3212 KB Output is correct
43 Correct 224 ms 1256 KB Output is correct
44 Correct 821 ms 2184 KB Output is correct
45 Execution timed out 1079 ms 2772 KB Time limit exceeded
46 Halted 0 ms 0 KB -