Submission #41172

#	Time	Username	Problem	Language	Result	Execution time	Memory
41172		ssnsarang2023	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	200 ms	2372 KiB

sculpture

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int oo = (int)1e9+7;
int n, lo, hi, f2[2005], f1[105][105];
ll sum[2005], a[2005];

int dp1(int i, int j, const ll &res, const int &lvl) {
	if (i == n + 1) return j == 0;
	if (f1[i][j] != -1) return f1[i][j];
	f1[i][j] = 0;
	for (int k = i + 1; k <= n + 1; ++k) {
		ll val = sum[i] - sum[k], tmp = ((val >> (ll)(lvl + 1)) << (ll)(lvl + 1));
		if ((res | tmp) == res && !((val >> (ll)lvl) & 1ll))
			f1[i][j] |= dp1(k, j - 1, res, lvl);
	}
	return f1[i][j];
}

int dp2(int i, const ll &res, const int &lvl) {
	if (i == n + 1) return hi + 1;
	if (f2[i] < oo) return f2[i];
	f2[i] = 0;
	for (int j = i + 1; j <= n + 1; ++j) {
		ll val = sum[i] - sum[j], tmp = ((val >> (ll)(lvl + 1)) << (ll)(lvl + 1));
		if ((res | tmp) == res && !((val >> (ll)lvl) & 1ll))
			f2[i] = max(f2[i], dp2(j, res, lvl) - 1);
	}
	return f2[i];
}

int main() {
	scanf("%d%d%d", &n, &lo, &hi);
	for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
	for (int i = n; i >= 1; --i) sum[i] = sum[i + 1] + a[i];
	ll res = 0;
	if (lo != 1) {
		for (int i = 36; i >= 0; --i) {
			memset(f1, -1, sizeof(f1));
			bool ok = false;
			for (int j = lo; j <= hi; ++j) if (dp1(1, j, res, i) == 1)
			{ ok = true; break; }
			if (!ok) res |= (1ll << (ll)i);
		}
	} else {
		for (int i = 40; i >= 0; --i) {
			fill(f2, f2 + n + 1, oo);
			int tmp = dp2(1, res, i);
			if (tmp < 1 || tmp >= oo) res |= (1ll << (ll)i);
		}
	}
	printf("%lld", res);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:40:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &lo, &hi);
                               ^
sculpture.cpp:41:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
                                                   ^

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