Submission #20158

#	Time	Username	Problem	Language	Result	Execution time	Memory
20158		berasogut	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	283 ms	25300 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (root+root)
#define sag (root+root+1)
#define orta ((bas+son)/2)
#define ll long long
#define pii pair<int,int>
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

const int N=2e3+5;
const int mod=1e9+7;
const int inf=1e9+7;

int n,a,b,i,j,k;
int dp[N][N],dp2[N];
ll A[N],t,ans;

char H[2005][2005],H2[2005][2005];

int f(int x,int s){

   if(x==n+1 and s>=a and s<=b)
      return 1;

   int &r=dp[x][s];

   if(r!=-1)
      return r;

   r=0;

   for(int i=x ; i<=n ; i++)
      if(H[x][i])
         r|=f(i+1,s+1);

   return r;
}

int f2(int x){
   if(x==n+1)
      return 0;

   int &r=dp2[x];

   if(r!=-1)
      return r;

   r=2005;

   for(int i=x ; i<=n ; i++)
      if(H[x][i])
         r=min(r,f2(i+1)+1);

   return r;
}

main(){

   scanf("%d %d %d",&n,&a,&b);

   for(i=1 ; i<=n ; i++){
      scanf("%lld",A+i);
      A[i]+=A[i-1];
      for(j=i ; j<=n ; j++)
         H[i][j]=1;
   }

   for(i=40 ; i>=0 ; i--){
      memcpy(H2,H,sizeof H);
      for(j=1 ; j<=n ; j++)
         for(k=j ; k<=n ; k++)
            if(H[j][k]){
               t=A[k]-A[j-1];
               if(t&(1LL<<i))
                  H[j][k]=0;
            }

      if(a==1){
         memset(dp2,-1,sizeof dp2);
         if(f2(1)>b){
            ans+=1LL<<i;
            memcpy(H,H2,sizeof H);
         }
      }
      else {
         memset(dp,-1,sizeof dp);
         if(!f(1,0)){
            ans+=1LL<<i;
            memcpy(H,H2,sizeof H);
         }
      }
   }

   printf("%lld",ans);

}

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