Submission #15678

#	Time	Username	Problem	Language	Result	Execution time	Memory
15678		cki86201	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	88 ms	1148 KiB

sculpture

#include<stdio.h>

const int INF = 123456;
typedef long long ll;
ll p[2002];
int dis[2002], dis2[102][102];
int n, a, b;

int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)scanf("%lld",p+i);
	for(int i=2;i<=n;i++)p[i] += p[i-1];
	ll ans = 0;
	if(a == 1){
		for(int i=40;i>=0;i--){
			for(int j=0;j<=n;j++)dis[j] = INF;
			dis[0] = 0;
			for(int j=0;j<=n;j++){
				if(dis[j] == INF)continue;
				for(int k=j+1;k<=n;k++){
					if(((ans | (1LL<<i)) & (p[k] - p[j])) == 0 && dis[j] + 1 < dis[k])dis[k] = dis[j] + 1;
				}
			}
			if(dis[n] <= b)ans |= (1LL<<i);
		}
	}
	else{
		for(int i=40;i>=0;i--){
			for(int j=0;j<=n;j++)for(int k=1;k<=b;k++)dis2[j][k] = 0;
			dis2[0][0] = 1;
			for(int j=0;j<=n;j++){
				for(int k=0;k<b;k++){
					if(dis2[j][k] == 0)continue;
					for(int u=j+1;u<=n;u++){
						if(((ans | (1LL<<i)) & (p[u] - p[j])) == 0)dis2[u][k+1] = 1;
					}
				}
			}
			for(int k=a;k<=b;k++){
				if(dis2[n][k]){
					ans |= (1LL<<i);
					break;
				}
			}
		}
	}
	printf("%lld",(1LL<<41) - 1 - ans);
	return 0;
}

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