oj.uz

Submission #554662

# Submission time Handle Problem Language Result Execution time Memory
554662 2022-04-29T04:31:48 Z kwongweng Bali Sculptures (APIO15_sculpture) C++17
46 / 100
 863 ms 80196 KB 
/*
Solution for APIO 2015 - Bali Sculpture
Tags : 
*/

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}
 
void solve(){
    int n, a, b; cin >> n >> a >> b;
    vector<ll> y(n+1); FOR(i,1,n+1) cin >> y[i];
    vector<ll> p(n+1); FOR(i,1,n+1) p[i] = p[i-1] + y[i];
    if (n<=20){
        //bitmask, O(n * 2^n)
        ll ans = MOD*MOD;
        FOR(mask,0,(1<<(n-1))){
            ll val = 0; int cnt = 0; int cur = 0;
            FOR(i,0,n-1){
                if (mask&(1<<i)){
                    cnt++;
                    val |= (p[i+1]-p[cur]);
                    cur = i+1; 
                }
            }
            cnt++; val |= (p[n]-p[cur]);
            if (a <= cnt && cnt <= b) ans = min(ans, val);
        }
        cout << ans << '\n';
        return;
    }
    // knapsack O(n^3 * b * max(y[i]))
    int ans = MOD;
    int max_a = n * 20 + 1;
    int dp[n+1][b+1][max_a];
    ms(dp,-1,sizeof(dp));
    FOR(i,1,n+1){
        dp[i][1][p[i]-p[0]] = 1;
    }
    FOR(j,2,b+1){
        FOR(i,2,n+1){
            FOR(k,1,i){
                int val = p[i]-p[k];
                FOR(l,0,max_a){
                    if (dp[k][j-1][l] != -1){
                        int new_val = l|val;
                        dp[i][j][new_val] = 1;
                    }
                }
            }
        }
    }
    FOR(l,0,max_a){
        bool sol = false;
        FOR(j,a,b+1){
            if (dp[n][j][l] == 1){
                cout<<l; sol = true;
                break;
            }
        }
        if (sol) break;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

sculpture.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
sculpture.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      | 
sculpture.cpp: In function 'void solve()':
sculpture.cpp:78:9: warning: unused variable 'ans' [-Wunused-variable]
   78 |     int ans = MOD;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 30 ms 300 KB Output is correct
9 Correct 29 ms 312 KB Output is correct
10 Correct 29 ms 312 KB Output is correct
11 Correct 29 ms 212 KB Output is correct
12 Correct 33 ms 312 KB Output is correct
13 Correct 30 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 4 ms 212 KB Output is correct
21 Correct 30 ms 296 KB Output is correct
22 Correct 31 ms 212 KB Output is correct
23 Correct 32 ms 212 KB Output is correct
24 Correct 31 ms 296 KB Output is correct
25 Correct 28 ms 212 KB Output is correct
26 Correct 31 ms 332 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 316 KB Output is correct
30 Correct 16 ms 212 KB Output is correct
31 Correct 30 ms 212 KB Output is correct
32 Correct 29 ms 212 KB Output is correct
33 Correct 30 ms 212 KB Output is correct
34 Correct 31 ms 320 KB Output is correct
35 Correct 29 ms 212 KB Output is correct
36 Correct 31 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 5 ms 212 KB Output is correct
8 Correct 30 ms 316 KB Output is correct
9 Correct 30 ms 212 KB Output is correct
10 Correct 29 ms 212 KB Output is correct
11 Correct 29 ms 212 KB Output is correct
12 Correct 29 ms 212 KB Output is correct
13 Correct 31 ms 292 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 5 ms 316 KB Output is correct
21 Correct 29 ms 212 KB Output is correct
22 Correct 30 ms 312 KB Output is correct
23 Correct 29 ms 212 KB Output is correct
24 Correct 33 ms 296 KB Output is correct
25 Correct 29 ms 212 KB Output is correct
26 Correct 31 ms 312 KB Output is correct
27 Correct 2 ms 980 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 2 ms 980 KB Output is correct
30 Correct 11 ms 3004 KB Output is correct
31 Correct 22 ms 4504 KB Output is correct
32 Correct 23 ms 4516 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 21 ms 4508 KB Output is correct
35 Correct 17 ms 3912 KB Output is correct
36 Correct 10 ms 2520 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 220 KB Output is correct
7 Correct 4 ms 220 KB Output is correct
8 Correct 30 ms 220 KB Output is correct
9 Correct 30 ms 220 KB Output is correct
10 Correct 29 ms 220 KB Output is correct
11 Correct 30 ms 220 KB Output is correct
12 Correct 30 ms 348 KB Output is correct
13 Correct 33 ms 220 KB Output is correct
14 Correct 3 ms 988 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 11 ms 2908 KB Output is correct
18 Correct 21 ms 4512 KB Output is correct
19 Correct 20 ms 4444 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 22 ms 4504 KB Output is correct
22 Correct 17 ms 3796 KB Output is correct
23 Correct 10 ms 2388 KB Output is correct
24 Correct 23 ms 4672 KB Output is correct
25 Correct 25 ms 4008 KB Output is correct
26 Correct 92 ms 11860 KB Output is correct
27 Correct 339 ms 36948 KB Output is correct
28 Correct 808 ms 80180 KB Output is correct
29 Correct 770 ms 80184 KB Output is correct
30 Correct 1 ms 1876 KB Output is correct
31 Correct 377 ms 38276 KB Output is correct
32 Correct 573 ms 59616 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Correct 29 ms 312 KB Output is correct
9 Correct 29 ms 212 KB Output is correct
10 Correct 29 ms 212 KB Output is correct
11 Correct 29 ms 312 KB Output is correct
12 Correct 29 ms 212 KB Output is correct
13 Correct 31 ms 336 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 4 ms 316 KB Output is correct
21 Correct 30 ms 316 KB Output is correct
22 Correct 28 ms 312 KB Output is correct
23 Correct 32 ms 212 KB Output is correct
24 Correct 29 ms 316 KB Output is correct
25 Correct 29 ms 212 KB Output is correct
26 Correct 30 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 15 ms 320 KB Output is correct
31 Correct 31 ms 212 KB Output is correct
32 Correct 30 ms 212 KB Output is correct
33 Correct 32 ms 296 KB Output is correct
34 Correct 32 ms 212 KB Output is correct
35 Correct 30 ms 300 KB Output is correct
36 Correct 33 ms 212 KB Output is correct
37 Correct 2 ms 960 KB Output is correct
38 Correct 2 ms 852 KB Output is correct
39 Correct 3 ms 980 KB Output is correct
40 Correct 10 ms 3000 KB Output is correct
41 Correct 20 ms 4512 KB Output is correct
42 Correct 20 ms 4416 KB Output is correct
43 Correct 0 ms 704 KB Output is correct
44 Correct 20 ms 4416 KB Output is correct
45 Correct 17 ms 3920 KB Output is correct
46 Correct 10 ms 2516 KB Output is correct
47 Correct 23 ms 4564 KB Output is correct
48 Correct 23 ms 4012 KB Output is correct
49 Correct 91 ms 11980 KB Output is correct
50 Correct 332 ms 37008 KB Output is correct
51 Correct 749 ms 80184 KB Output is correct
52 Correct 759 ms 80196 KB Output is correct
53 Correct 1 ms 1856 KB Output is correct
54 Correct 402 ms 38260 KB Output is correct
55 Correct 571 ms 59604 KB Output is correct
56 Runtime error 7 ms 9208 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 5 ms 212 KB Output is correct
8 Correct 30 ms 212 KB Output is correct
9 Correct 32 ms 300 KB Output is correct
10 Correct 28 ms 212 KB Output is correct
11 Correct 30 ms 292 KB Output is correct
12 Correct 30 ms 316 KB Output is correct
13 Correct 30 ms 320 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 16 ms 320 KB Output is correct
18 Correct 28 ms 212 KB Output is correct
19 Correct 29 ms 212 KB Output is correct
20 Correct 29 ms 212 KB Output is correct
21 Correct 30 ms 212 KB Output is correct
22 Correct 32 ms 308 KB Output is correct
23 Correct 30 ms 212 KB Output is correct
24 Correct 2 ms 980 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 980 KB Output is correct
27 Correct 11 ms 3004 KB Output is correct
28 Correct 22 ms 4412 KB Output is correct
29 Correct 20 ms 4424 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 20 ms 4436 KB Output is correct
32 Correct 17 ms 3796 KB Output is correct
33 Correct 11 ms 2388 KB Output is correct
34 Correct 22 ms 4680 KB Output is correct
35 Correct 24 ms 3924 KB Output is correct
36 Correct 96 ms 11860 KB Output is correct
37 Correct 353 ms 37044 KB Output is correct
38 Correct 863 ms 80104 KB Output is correct
39 Correct 817 ms 80184 KB Output is correct
40 Correct 1 ms 1876 KB Output is correct
41 Correct 381 ms 38176 KB Output is correct
42 Correct 584 ms 59624 KB Output is correct
43 Runtime error 9 ms 9260 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -