Submission #32261

#	Time	Username	Problem	Language	Result	Execution time	Memory
32261		cscandkswon	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	109 ms	5068 KiB

sculpture

#include <cstdio>
#include <cstring>
const int MAXN = 2005, INF=1e9;
typedef long long ll;

int N, A, B;
ll T;
int Y[MAXN], DP[MAXN];
bool D[MAXN][MAXN];
ll S[MAXN];

int check1(ll n) {
	int i, j;
	for (i = 1; i <= N; i++) DP[i] = INF;
	for (i = 1; i <= N; i++) {
		for (j = 0; j < i; j++) {
			if (DP[i] < DP[j] + 1) continue;
			if (((S[i] - S[j]) | n) == n) DP[i] = DP[j] + 1;
		}
	}
	if (DP[N] <= B) return 0;
	return 1;
}

int check2(ll n) {
	int i, j, k;
	memset(D, 0, sizeof D);
	D[0][0] = 1;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= i; j++) {
			for (k = 0; k < i; k++) if (D[k][j - 1]) {
				if (((S[i] - S[k]) | n) == n) D[i][j] = 1;
			}
		}
	}
	for (i = A; i <= B; i++) if (D[N][i]) return 0;
	return 1;
}

int check(ll n) {
	if (A == 1) return check1(n);
	return check2(n);
}

int main() {
	int i;
	scanf("%d %d %d", &N, &A, &B);
	for (i = 1; i <= N; i++) scanf("%d", Y + i);
	for (i = 1; i <= N; i++) S[i] = S[i - 1] + Y[i];
	for (i = 50; i >= 0; i--) {
		if (check(T + (1LL << i) - 1)) {
			T += (1LL << i);
		}
	}
	printf("%lld", T);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:47:31: 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:48:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= N; i++) scanf("%d", Y + i);
                                             ^

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