Submission #754250

#	Time	Username	Problem	Language	Result	Execution time	Memory
754250		1bin	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	79 ms	432 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
ll n, a[2005], A, B, dp1[105][105], dp[2005], ans;

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n <= 100){
        ll mask = (1LL << 41) - 1;
        for(int b = 40; b >= 0; b--){
            memset(dp1, 0, sizeof(dp1));
            dp1[0][0] = 1;
            mask ^= 1LL << b;
            for(int i = 1; i <= n; i++){
                ll v = a[i];
                for(int j = i - 1; j >= 0; j--){
                    if((mask | v) == mask)
                        for(int k = B; k; k--) dp1[i][k] |= dp1[j][k - 1];
                    v += a[j];
                }
            }

            int f = 0;
            for(int j = A; j <= B; j++) f |= dp1[n][j];
            if(!f){
                mask ^= 1LL << b;
                ans += 1LL << b;
            }
        }
    }
    else{
        ll mask = (1LL << 41) - 1;
        for(int b = 40; b >= 0; b--){
            mask ^= 1LL << b;
            for(int i = 1; i <= n; i++){
                ll v = a[i];
                dp[i] = n + 1;
                for(int j = i - 1; j >= 0; j--){
                    if((mask | v) == mask) dp[i] = min(dp[i], dp[j] + 1);
                    v += a[j];
                }
            }
            if(dp[n] > B) {
                mask ^= 1LL << b;
                ans += 1LL << b;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29