Submission #231025

#	Time	Username	Problem	Language	Result	Execution time	Memory
231025		peijar	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	483 ms	504 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;
}

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

	read_in();
	solve_a1();
}

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