Submission #1166231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166231		salmon	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	165 ms	444 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

int N,A,B;
int lst[2100];
long long int pre[2100];
int memo[2100];
bitset<110> arr[110];

int main(){
		
	scanf(" %d",&N);
	scanf(" %d",&A);
	scanf(" %d",&B);
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&lst[i]);
	}
	
	pre[0] = 0;
	
	for(int i = 1; i <= N; i++){
		pre[i] = pre[i - 1] + lst[i];
	}
	
	if(N <= 100){
		
		long long int ans = (1LL<<60) - 1; 
		
		arr[0].reset();
		arr[0].set(0);
		
		for(int k = 59; k >= 0; k--){
			
			ans -= (1LL<<k);
			
			for(int i = 1; i <= N; i++){
				arr[i].reset();
				for(int j = 0; j < i; j++){
					if( ((pre[i] - pre[j]) | ans) <= ans) arr[i] |= (arr[j]<<1);
				}
			}
			
			bool win = false;
			
			for(int i = A; i <= B; i++) win |= arr[N][i];
			
			if(!win) ans += (1LL<<k);
		}
		
		printf("%lld",ans);
		
	}
	else{
		long long int ans = (1LL<<60) - 1; 
		
		memo[0] = 0;
		
		for(int k = 59; k >= 0; k--){
			
			ans -= (1LL<<k);
			
			for(int i = 1; i <= N; i++){
				memo[i] = N + 1;
				for(int j = 0; j < i; j++){
					if( ((pre[i] - pre[j]) | ans) <= ans){
						memo[i] = min(memo[i],memo[j] + 1);
					}
				}
			}
			
			if(memo[N] > B){
				ans += (1LL<<k);
			}
		}
		
		printf("%lld",ans);
	}
	
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
sculpture.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf(" %d",&A);
      |         ~~~~~^~~~~~~~~~
sculpture.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf(" %d",&B);
      |         ~~~~~^~~~~~~~~~
sculpture.cpp:17:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~

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