Submission #241003

#TimeUsernameProblemLanguageResultExecution timeMemory
241003pavementBali Sculptures (APIO15_sculpture)C++17
100 / 100
438 ms632 KiB
#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], dp2[2005];
char mem[2005][2005];
vector<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;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> A >> B;
	if (N > 100) assert(A == 1);
	for (int i = 1; i <= N; i++) cin >> Y[i], P[i] = Y[i] + P[i - 1];
	for (int i = 41; i >= 0; i--) {
		S.pb(i);
		bool yes = 0;
		if (A > 1) {
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= B; j++)
					mem[i][j] = -1;
			for (int j = A; j <= B; j++)
				if (dp(N, j)) {
					yes = 1;
					break;
				}
		} else {
			for (int j = 1; j <= N; j++) {
				dp2[j] = 1e9;
				for (int k = 0; k < j; k++) {
					bool inv = 0;
					for (int l : S)
						if ((P[j] - P[k]) & (1ll << l)) {
							inv = 1;
							break;
						}
					if (!inv) dp2[j] = min(dp2[j], dp2[k] + 1);
				}
			}
			yes = dp2[N] <= B;
		}
		if (!yes) S.ppb(), 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:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...