Submission #243663

#	Time	Username	Problem	Language	Result	Execution time	Memory
243663		GREGOIRELC	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1092 ms	14512 KiB

sculpture

#include <iostream>

using namespace std;

#define int long long

const int MAX_STATUE = 2000 + 1;
const int MAX_BITS = 41;

int nbStatue;
int minBar, maxBar;
int valStatue[MAX_STATUE];
int cumul[MAX_STATUE];
int dp[MAX_STATUE][MAX_STATUE];
int curNb = 0;

bool estOblige(int curBit)
{
	int maxi = curNb + (1ll << curBit);
	dp[0][0] = curBit + 1;
	for(int iPos = 1; iPos <= nbStatue; iPos++)
	{
		for(int iDeb = 0; iDeb < iPos; iDeb++)
		{
			//cout << (curNb | (cumul[iPos] - cumul[iDeb])) << " " << maxi << endl;
			if((curNb | (cumul[iPos] - cumul[iDeb])) < maxi)
			{
				for(int k = 0; k < maxBar; k++)
				{
					if(dp[iDeb][k] == curBit + 1)
					{
						dp[iPos][k + 1] = curBit + 1;
					}
				}
			}
		}
	}
	for(int k = minBar; k <= maxBar; k++)
	{
		if(dp[nbStatue][k] == curBit + 1)
		{
			return false;
		}
	}
	return true;
}

int32_t main()
{
	ios::sync_with_stdio(false);

	cin >> nbStatue >> minBar >> maxBar;
	for(int iStatue = 1; iStatue <= nbStatue; iStatue++)
	{
		cin >> valStatue[iStatue];
		cumul[iStatue] += cumul[iStatue - 1];
		cumul[iStatue] += valStatue[iStatue];
	}
	for(int iBit = MAX_BITS; iBit > -1; iBit--)
	{
		if(estOblige(iBit))
		{
			//cout << iBit << endl;
			curNb += (1ll << iBit);
		}
	}
	cout << curNb << endl;
}

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