Submission #20159

#	Time	Username	Problem	Language	Result	Execution time	Memory
20159		ykaya	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	373 ms	64668 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define ll long long
#define N (int)(1e5+10)
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define nd second
#define st first
#define inf mod
#define endl '\n'
#define sag (sol|1)
#define sol (root<<1)
#define ort ((bas+son)>>1)
#define bit(x,y) ((x>>y)&1)
#define int long long

int dp1[2004],dp2[105][105];
int i,j,k,n,m,x,y,z,H[2005][2005];
int temp[2005][2005],pre[2005];
int a,b,A[2004],ans;

bool f1(){

   memset(dp1,5,sizeof dp1);

   dp1[n+1] = 0;


   for(int x=n ; x>=1 ; x--)
      for(int y=n ; y>=x ; y--)
         if(H[x][y])
            dp1[x] = min(dp1[y+1]+1,dp1[x]);

   return dp1[1]<=b;
}

bool f2(){
   memset(dp2,0,sizeof dp2);

   dp2[n+1][0] = 1;

   for(int x=n ; x>=1 ; x--)
      for(int k=b ; k>=1 ; k--)
         for(int y=n ; y>=x ; y--)
            if(H[x][y])
               dp2[x][k] |= dp2[y+1][k-1];

   bool ans=0;

   for(int i=a ; i<=b ; i++)
      ans |= dp2[1][i];

   return ans;
}

main(){
   cin >> n >> a >> b;

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

   for(i=1 ; i<=n ; i++)
      for(j=i ; j<=n ; j++)
         H[i][j] = 1;

   for(i=40 ; i>=0 ; i--){
      for(int x=1 ; x<=n ; x++)
         for(int y=x ; y<=n ; y++) {
            temp[x][y] = H[x][y];
            if(H[x][y] and ((1ll << i) & (pre[y] - pre[x - 1])))
               H[x][y] = 0;
         }

      if(a == 1 and f1())
         continue;
      if(a != 1 and f2())
         continue;

      ans += (1LL<<i);

      for(int x=1 ; x<=n ; x++)
         for(int y=x ; y<=n ; y++)
            H[x][y] = temp[x][y];
   }

   cout << ans << endl;

}

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