Submission #64266

#	Time	Username	Problem	Language	Result	Execution time	Memory
64266		kingpig9	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	123 ms	2468 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2018;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, A, B;
ll P[MAXN];
int dp[MAXN];
bitset<MAXN> msk[MAXN];

bool can (ll cur, int pos, ll s) {
	return (s ^ (s & cur)) < (1ll << pos);
}

bool moo (ll cur, int pos) {
	//try NOT to add pos.
	//But at the same time, keep the leading bits.

	//is it possible to do it in this amount?
	if (A == 1) {
		//need N^2, not N^3 / 32.
		dp[0] = 0;
		for (int i = 1; i <= N; i++) {
			dp[i] = MAXN;
			for (int j = 0; j < i; j++) {
				ll s = P[i] - P[j];
				//s, cur, pos are what matter.
				//whatever s has and cur does not have.
				//110101........	(cur)
				//      p        
				//  c c c
				//"c"s indicate the bits that can't be set
				//note that c is also at the first dot.
				if (can(cur, pos, s)) {
					dp[i] = min(dp[i], dp[j] + 1);
				}
			}
		}
		return dp[N] <= B;
	} else {
		msk[0][0] = 1;
		for (int i = 1; i <= N; i++) {
			msk[i].reset();
			for (int j = 0; j < i; j++) {
				ll s = P[i] - P[j];
				if (can(cur, pos, s)) {
					msk[i] |= (msk[j] << 1);
				}
			}
		}

		for (int i = A; i <= B; i++) {
			if (msk[N][i]) {
				return true;
			}
		}
		return false;
	}
}

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

	ll ans = 0;
	for (int i = 42; i >= 0; i--) {
		if (!moo(ans, i)) {
			ans ^= (1ll << i);
		}
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:72: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &P[i]);
   ~~~~~^~~~~~~~~~~~~~~

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