Submission #14390

#	Time	Username	Problem	Language	Result	Execution time	Memory
14390		kriii	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	99 ms	1116 KiB

sculpture

#include <stdio.h>

int N,A,B,G[2020]; long long X[2020]; bool gr[101][101];

int main()
{
	scanf ("%d %d %d",&N,&A,&B);
	for (int i=1;i<=N;i++){
		scanf ("%lld",&X[i]);
		X[i] += X[i-1];
	}

	if (A == 1){
		long long ans = 0;
		for (int k=40;k>=0;k--){
			long long want = ans + (1ll << k) - 1;
			for (int i=1;i<=N;i++) G[i] = 10000;
			for (int j=1;j<=N;j++) for (int i=1;i<=j;i++){
				long long see = X[j] - X[i-1];
				if ((see | want) == want){
					if (G[j] > G[i-1] + 1)
						G[j] = G[i-1] + 1;
				}
			}
			if (G[N] > B) ans += (1ll << k);
		}
		printf ("%lld\n",ans);
	}
	else{
		long long ans = 0;
		for (int k=40;k>=0;k--){
			long long want = ans + (1ll << k) - 1;
			gr[0][0] = 1;
			for (int i=1;i<=N;i++) for (int j=0;j<=B;j++) gr[j][i] = 0;
			for (int j=1;j<=N;j++) for (int i=1;i<=j;i++){
				long long see = X[j] - X[i-1];
				if ((see | want) == want){
					for (int l=0;l<B;l++) if (gr[l][i-1]) gr[l+1][j] = 1;
				}
			}
			bool good = 0;
			for (int i=A;i<=B;i++) if (gr[i][N]) good = 1;
			if (!good) ans += (1ll << k);
		}
		printf ("%lld\n",ans);
	}

	return 0;
}

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