Submission #146391

#	Time	Username	Problem	Language	Result	Execution time	Memory
146391		songc	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	213 ms	4548 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, A, B;
LL S[2020];
bool chk[2020][2020];
int D[2020];

int main(){
	scanf("%d %d %d", &N, &A, &B);
	for (int i=1; i<=N; i++){
		scanf("%lld", &S[i]);
		S[i] += S[i-1];
	}
	if (A == 1){
		LL ans = (1ll<<60)-1;
		for (int i=59; i>=0; i--){
			ans ^= (1ll<<i);
			memset(D, 1, sizeof D);
			D[0] = 0;
			for (int j=1; j<=N; j++) for (int k=0; k<j; k++) if ((ans | (S[j]-S[k])) == ans) D[j] = min(D[j], D[k]+1);
			if (D[N] > B) ans ^= (1ll<<i);
		}
		printf("%lld\n", ans);
	}
	else{
		LL ans = (1ll<<60)-1;
		for (int i=59; i>=0; i--){
			ans ^= (1ll<<i);
			memset(chk, false, sizeof chk);
			chk[0][0] = true;
			for (int j=1; j<=N; j++) for (int k=1; k<=j; k++){
				for (int l=0; l<j; l++) if ((ans | (S[j]-S[l])) == ans) chk[j][k] = chk[j][k] || chk[l][k-1];
			}
			bool tf = true;
			for (int j=A; j<=B; j++) if (chk[N][j]) tf = false;
			if (tf) ans ^= (1ll<<i);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

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

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