Submission #74722

#	Time	Username	Problem	Language	Result	Execution time	Memory
74722		goodbaton	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	40 ms	2208 KiB

sculpture

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

typedef long long ll;
#define SIZE 2000
#define INF 2000000000
#define LLINF 4000000000000000000LL


int N,A,B;
bool dp[SIZE+1][SIZE];
int dp5[SIZE+1];
ll Y[SIZE+1];

ll dfs5(int h,ll ksum){
    
    if(h<0) return ksum;
    
    ll ksumaf = ksum - (1LL<<h);
    
    for(int i=0;i<=N;i++)
            dp5[i]=INF;
    
    dp5[0]=0;
    
    for(int i=0;i<N;i++){
        if(dp5[i]==INF) continue;
        
        for(int j=i+1;j<=N;j++){
            if(Y[j]-Y[i] > ksumaf) break;
                if(((Y[j]-Y[i]) | ksumaf) == ksumaf)
                    dp5[j]=min(dp5[j],dp5[i]+1);
        }
    }
    
    if(dp5[N]<=B)
        return dfs5(h-1,ksumaf);
    
    return dfs5(h-1,ksum);
}


ll dfs(int h,ll ksum){
    
    if(h<0) return ksum;
    
    ll ksumaf = ksum - (1LL<<h);
    
    for(int i=0;i<=N;i++)
        for(int j=0;j<=N;j++)
            dp[i][j]=false;
    
    dp[0][0]=true;
    
    for(int k=0;k<B;k++){
        for(int i=0;i<N;i++){
            if(dp[k][i]==false) continue;
            
            for(int j=i+1;j<=N;j++){
                if(Y[j]-Y[i] > ksumaf) break;
                if(((Y[j]-Y[i]) | ksumaf) == ksumaf)
                    dp[k+1][j]=true;
            }
        }
    }
    
    
    for(int i=A;i<=B;i++){
        if(dp[i][N]==true)
            return dfs(h-1,ksumaf);
    }
    
    return dfs(h-1,ksum);
}

int main(){
    int b=0; //b2 = 2^b
    ll b2;
    
    scanf("%d%d%d",&N,&A,&B);
    
    for(int i=1;i<=N;i++){
        scanf("%lld",&Y[i]);
        
        Y[i]+=Y[i-1];
    }
    
    for(b2=1;b2<=Y[N];b2*=2)
        b++;
    
    if(A==1)
        printf("%lld\n",dfs5(b-1,b2-1));
    else
        printf("%lld\n",dfs(b-1,b2-1));
    
    return 0;
}

Compilation message (stderr)

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

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