Submission #582529

#	Time	Username	Problem	Language	Result	Execution time	Memory
582529		gg123_pe	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	76 ms	340 KiB

sculpture

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<ll,ll> ii; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 2005; 
const ll inf = 1e9;


int n, A, B, DP[2005]; 
bool dp[105][105]; 
ll a[2005]; 

int main(){
    cin >> n >> A >> B; 

    f(i,1,n+1) cin >> a[i];
    
    if(n <= 100){
        ll ans = (1LL<<37) - 1;

        fa(ij,36,0){
            ans ^= (1LL<<ij); 
            
            f(i,1,n+1) f(j,1,i+1) dp[i][j] = 0; 
            dp[0][0] = 1;  

            f(i,1,n+1){
                ll s = 0; 
                fa(j,i,1){
                    s += a[j]; 
                    if((s|ans) != ans) continue; 
                    f(k,1,i+1) 
                        if(dp[j-1][k-1]) dp[i][k] = 1;
                }
            }
            bool fe = 0; 
            f(j,A,B+1) fe |= dp[n][j]; 

            if(!fe) ans ^= (1LL<<ij); 
        } 
        cout << ans << "\n"; 
        return 0; 
    }
    ll ans = (1LL<<41) - 1;

    fa(ij,40,1){
        ans ^= (1LL<<ij); 

        DP[0] = 0; 
        f(i,1,n+1) DP[i] = n+1; 

        f(i,1,n+1){
            ll s = 0; 
            fa(j,i,1){
                s += a[j]; 
                if((s|ans) != ans) continue; 
                DP[i] = min(DP[i], DP[j-1] + 1);
            }
        }
        if(DP[n] > B) ans ^= (1LL<<ij); 
    }
    cout << ans << "\n"; 
    return 0; 
}

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