Submission #241001

#	Time	Username	Problem	Language	Result	Execution time	Memory
241001		pavement	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1058 ms	4600 KiB

sculpture

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef TEST
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define ins insert
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
int ans, N, A, B, Y[2005], P[2005], mem2[2005];
char mem[2005][2005];
set<int> S;

bool dp(int n, int x) {
	if (x < 0) return 0;
	if (n == 0) return x == 0;
	if (mem[n][x] != -1) return mem[n][x];
	bool r = 0;
	for (int i = 0; i < n; i++) {
		bool inv = 0;
		for (int j : S)
			if ((P[n] - P[i]) & (1ll << j)) {
				inv = 1;
				break;
			}
		if (!inv) r |= dp(i, x - 1);
	}
	return mem[n][x] = r;
}

int dp2(int n) {
	if (n == 0) return 0;
	if (mem2[n] != -1) return mem2[n];
	int r = 1e9;
	for (int i = 0; i < n; i++) {
		bool inv = 0;
		for (int j : S)
			if ((P[n] - P[i]) & (1ll << j)) {
				inv = 1;
				break;
			}
		if (!inv) r = min(r, dp2(i) + 1);
	}
	return mem2[n] = r;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> A >> B;
	for (int i = 1; i <= N; i++) cin >> Y[i], P[i] = Y[i] + P[i - 1];
	for (int i = 41; i >= 0; i--) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= B; j++)
				mem[i][j] = -1;
			mem2[i] = -1;
		}
		S.insert(i);
		bool yes = 0;
		if (A > 1) {
			for (int j = A; j <= B; j++)
				if (dp(N, j)) {
					yes = 1;
					break;
				}
		} else {
			yes = dp2(N) <= B;
		}
		if (!yes) S.erase(i), ans |= (1ll << i);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

sculpture.cpp: In function 'bool dp(long long int, long long int)':
sculpture.cpp:49:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return mem[n][x] = r;
         ~~~~~~~~~~^~~
sculpture.cpp: At global scope:
sculpture.cpp:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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