Submission #49443

#	Time	Username	Problem	Language	Result	Execution time	Memory
49443		wzy	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	427 ms	24496 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n , a , b;
int v[3000];
int c[2500][2500];
bool dp[2500][2500];
int mask;
bool vis[2500][2500];
int cg[2500];

bool can(int i , int j){
	if(i == n + 1){
		if(a <= j && j <= b) return 1;
		else return 0;
	}
	if(vis[i][j]) return dp[i][j];
	vis[i][j] = 1;
	for(int w = i  ; w <= n ; w++){
		if((c[i][w] & mask) == 0){
			dp[i][j] = max(dp[i][j] , can(w + 1 , j + 1));
		}
	}
	return dp[i][j];
}


int32_t main(){
	scanf("%lld%lld%lld" , &n , &a , &b);
	for(int i = 1 ; i <= n; i ++) scanf("%lld" , &v[i]);
	for(int i = 1 ; i <= n; i ++){
		c[i][i] = v[i];
		for(int j = i + 1 ; j <= n; j ++) c[i][j] = c[i][j-1] + v[j];
	}
		int dontpick = 0;
	if(a != 1){
		for(int j = 40 ; j >= 0 ; j--){
			mask = dontpick  + (1LL<<j);
			for(int i = 0 ; i <= 300 ; i++)
				for(int j = 0 ; j <= 300 ; j++) dp[i][j] = 0 , vis[i][j] = 0;
			dontpick += (1LL<<j) * can(1 , 0);
		}
		int U = (1LL<<41) - 1;
		printf("%lld\n" , U ^ dontpick);
	}
	else{
		for(int j = 40 ; j >=0 ; j--){
			mask = dontpick + (1LL<<j);
			for(int i = 0 ; i <= n ; i++){
				cg[i] = 10000000;
			}
			cg[0] = 0;
			for(int i = 1 ; i <= n ; i ++){
				for(int jw = i ; jw >= 1 ; jw--){
					if((c[jw][i] & mask) == 0){
						cg[i] = min(cg[jw-1] + 1 , cg[i]);
					}
				}
			}
			if(cg[n] <= b){
				dontpick += (1LL<<j);
			}
		}
		int U = (1LL<<41) - 1;
		printf("%lld\n" , U ^ dontpick); 
	}
}

Compilation message (stderr)

sculpture.cpp: In function 'int32_t main()':
sculpture.cpp:29:7: 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:30:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i <= n; i ++) scanf("%lld" , &v[i]);
                                ~~~~~^~~~~~~~~~~~~~~~

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