Submission #146006

#	Time	Username	Problem	Language	Result	Execution time	Memory
146006		str0ct	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	212 ms	504 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll N,A,B;
ll arr[2020];
ll ans;
ll dp2[105][105];
ll dp[2020];
void sol1(){
    ll k=60;
    ans=(1LL<<k)-1LL;
    k--;
    while(k>=0){
        ans-=(1LL<<k);
        fill(dp+1,dp+2005,2080);
        dp[0]=0;
        for(ll i=1;i<=N;i++){
            for(ll j=0;j<i;j++)if(((arr[i]-arr[j])|ans)==ans)dp[i]=min(dp[i],dp[j]+1);
        }
        if(dp[N]>B)ans+=(1LL<<k);
        k--;
    }
}
void sol2(){
    ll k=60;
    ans=(1LL<<k)-1LL;
    k--;
    while(k>=0){
        for(int i=0;i<105;i++)for(int j=0;j<105;j++)dp2[i][j]=0;
        dp2[0][0]=1;
        ans-=(1LL<<k);
        for(ll i=1;i<=N;i++)
            for(ll j=1;j<=i;j++)
                for(ll p=0;p<i;p++)
                    if(dp2[p][j-1]&&((arr[i]-arr[p])|ans)==ans)dp2[i][j]=1;
        ll flag=0;
        for(ll i=A;i<=B;i++){
            if(dp2[N][i]){
                flag=1;
                break;
            }
        }
        if(flag==0)ans+=(1LL<<k);
        k--;
    }
}
int main(){
    scanf("%lld%lld%lld",&N,&A,&B);
    for(ll i=1;i<=N;i++){
        scanf("%lld",arr+i);
        arr[i]+=arr[i-1];
    }
    if(A==1)sol1();
    else sol2();
    printf("%lld",ans);
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&N,&A,&B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",arr+i);
         ~~~~~^~~~~~~~~~~~~~

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