Submission #231029

#	Time	Username	Problem	Language	Result	Execution time	Memory
231029		peijar	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	516 ms	552 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXP = 60;

int nb_sculptures, min_parti, max_parti;
vector<ll> valeur;

void read_in()
{
	cin >> nb_sculptures >> min_parti >> max_parti;
	valeur.resize(nb_sculptures);

	for (auto &v : valeur)
		cin >> v;
}

void solve_a1(void)
{
	ll cur_prefix=0;
	ll mask=0;
	auto try_prefix = [&](void) 
	{
		vector<int> dp(nb_sculptures+1);
		dp[nb_sculptures] = 0;
		for (int i(nb_sculptures-1); i >= 0; --i)
		{
			dp[i] = 1e9;
			ll sum(0);
			for (int nxt(i); nxt < nb_sculptures; ++nxt)
			{
				sum += valeur[nxt];
				if (((sum & mask) & cur_prefix) == (sum & mask))
					dp[i] = min(dp[i], 1 + dp[nxt+1]);
			}
		}
		return dp[0] <= max_parti;
	};

	for (ll p(MAXP-1); p >= 0; --p)
	{
		mask += (1LL<<p);
		if (!try_prefix())
			cur_prefix += (1LL<<p);
		assert(try_prefix());
	}
	cout << cur_prefix << endl;
}

void solve_a2(void)
{
	ll cur_prefix = 0;
	ll mask=0;
	auto try_prefix = [&](void)
	{
		vector<vector<bool>> dp(nb_sculptures+1, vector<bool>(max_parti+1));
		dp[nb_sculptures][0] = true;
		for (int i(nb_sculptures-1); i >= 0; --i)
			for (int nb_parti(1); nb_parti <= max_parti; ++nb_parti)
			{
				ll sum(0);
				for (int nxt(i); nxt < nb_sculptures; ++nxt)
				{
					sum += valeur[nxt];
					if (((sum & mask) & cur_prefix) == (sum & mask))
						dp[i][nb_parti] = dp[i][nb_parti] | dp[nxt+1][nb_parti-1];
				}
			}
		bool ret = false;
		for (int nb_parti(min_parti); nb_parti <= max_parti; ++nb_parti)
			ret = ret | dp[0][nb_parti];
		return ret;
	};

	for (ll p(MAXP-1); p >= 0; --p)
	{
		mask += (1LL<<p);
		if (!try_prefix())
			cur_prefix += (1LL<<p);
		assert(try_prefix());
	}
	cout << cur_prefix << endl;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	read_in();
	if (min_parti >= 2)
		solve_a2();
	else
		solve_a1();
}

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