Submission #108255

#	Time	Username	Problem	Language	Result	Execution time	Memory
108255		kek	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	190 ms	512 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define all(v) v.begin(), v.end()
#define len(v) ((int)(v).size())
#define pb push_back
#define kek pop_back
#define pii pair<int, int>
#define mp make_pair

#define debug(x) cout << #x << " = " << x << endl;

const int INF = 1e18 + 666;

template<class t1, class t2>
bool cmin(t1 &a, const t2 &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<class t1, class t2>
bool cmax(t1 &a, const t2 &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

#ifndef LOCAL
void UseFiles(const string &s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
#else
void UseFiles(const string&) {}
#endif

void run();

signed main() {
	// UseFiles("cowboys");
	iostream::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

int can_get(int cur, int bit, const vector<int> &v, int a, int b) {
	int n = len(v);
	vector<int> pref(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + v[i];
	}
	vector<vector<int>> dp(b + 1, vector<int>(n + 1, 0));
	dp[0][0] = 1;
	for (int i = 1; i <= b; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int k = 0; k < j; ++k) {
				int sm = pref[j] - pref[k];
				if (((sm | cur) >> bit) == (cur >> bit)) {
					dp[i][j] |= dp[i - 1][k];
				}
			}
		}
	}
	int ans = 0;
	for (int i = a; i <= b; ++i) {
		ans |= dp[i].back();
	}
	return ans;
}

int get_min_blocks(const vector<int> &v, int cur, int bit) {
	int n = len(v);
	vector<int> pref(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + v[i];
	}
	vector<int> dp(n + 1, INF);
	dp[0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			int sm = pref[i] - pref[j];
			if (((sm | cur) >> bit) == (cur >> bit)) {
				cmin(dp[i], dp[j] + 1);
			}
		}
	}
	return dp.back();
}

void run() {
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> v(n);
	for (auto &x : v) {
		cin >> x;
	}
	int cur = 0;
	if (a != 1) {
		for (int i = 43; i > -1; --i) {
			// cur |= (1 << i);
			if (!can_get(cur, i, v, a, b)) {
				cur |= (1ll << i);
				// assert(can_get(cur, i, v, a, b));
			}
		}
	} else {
		for (int i = 43; i > -1; --i) {
			if (get_min_blocks(v, cur, i) > b) {
				cur |= (1ll << i);
			}
		}
	}
	cout << cur << endl;
}

Compilation message (stderr)

sculpture.cpp: In function 'void UseFiles(const string&)':
sculpture.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((s + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((s + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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