Submission #1025325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025325		xnqs	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	311 ms	848 KiB

sculpture

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>

int x, min_cap, max_cap;
int64_t arr[2005];
int64_t pfx[2005];

inline int64_t sum_query(int l, int r) {
	return pfx[r] - ((l-1>=0) ? pfx[l-1] : 0);
}

bool can_solve(int64_t mask, int bit) {
	if (min_cap==1) {
		std::vector<int> dp(x, -1);
		const std::function<int(int)> sol = [&](int pos) {
			if (pos==x) return 0;
			if (dp[pos]!=-1) return dp[pos];

			int& ret = (dp[pos] = 0x3f3f3f3f);
			for (int i = pos; i < x; i++) {
				int64_t sum = sum_query(pos,i);
				if (((mask>>bit)|(sum>>bit))==(mask>>bit)) {
					ret = std::min(ret, 1+sol(i+1));
				}
			}

			return ret;
		};

		return sol(0) <= max_cap;
	}
	else {
		std::vector<std::vector<char>> dp(x, std::vector<char>(max_cap+1, -1));
		const std::function<bool(int,int)> sol = [&](int pos, int k) {
			if (k>max_cap) return false;
			if (pos==x) return min_cap <= k && k <= max_cap;
			if (dp[pos][k]!=-1) return static_cast<bool>(dp[pos][k]);

			char& ret = (dp[pos][k] = 0);
			for (int i = pos; i < x; i++) {
				int64_t sum = sum_query(pos,i);
				if (((mask>>bit)|(sum>>bit))==(mask>>bit)) {
					ret |= sol(i+1,k+1);
				}
			}

			return static_cast<bool>(ret);
		};

		return sol(0,0);
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> min_cap >> max_cap;
	for (int i = 0; i < x; i++) {
		std::cin >> arr[i];
		pfx[i] = pfx[i-1] + arr[i];
	}

	int64_t ans = 0;
	for (int bit = 60; bit >= 0; bit--) {
		if (!can_solve(ans,bit)) {
			ans |= (1LL<<bit);
		}
	}

	std::cout << ans << "\n";
}

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