Submission #120541

#	Time	Username	Problem	Language	Result	Execution time	Memory
120541		Runtime_error_	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	220 ms	632 KiB

sculpture

//APIO 2015 Bali Sculptures
//1-5 subtasks solution 100 points
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e3+9,MX=1e9+9;
ll n,x,y,a[N],pre[N],dp[N];
ll ans ;

ll solve(ll pos){

    if( pos == n+1)
        return  0;

    ll &ret=dp[pos];
    if(ret != -1)
        return ret;
    ret = MX;
    for(ll i=pos;i<=n;i++)
        if( ( (pre[i]-pre[pos-1]) | ans ) == ans )// we don't want set-bits that are not set in ans
            ret = min(ret,1+solve(i+1) ) ;
    return ret;
}

int main(){

    cin>>n>>x>>y;
    for(ll i=1;i<=n;i++)
        cin>>a[i],pre[i]=a[i]+pre[i-1];

    ans = (1ll<<61)-1;
    for(ll i=60;i>=0;i--){
        memset(dp,-1,sizeof(dp));
        ans-=(1ll<<i);
        if(solve(1)>y)
            ans+=(1ll<<i);
    }
    cout<<ans<<endl;
}

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