Submission #243666

#TimeUsernameProblemLanguageResultExecution timeMemory
243666GREGOIRELCBali Sculptures (APIO15_sculpture)C++14
100 / 100
137 ms1152 KiB
#include <iostream>

using namespace std;

#define int long long

const int MAX_STATUE = 2000 + 1;
const int MAX_BITS = 41;
const int INF = 1e9 + 7;

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);
	if(minBar == 1)
	{
		for(int i = 0; i <= nbStatue; i++)
		{
			dp[curBit][i] = INF;
		}
		dp[curBit][0] = 0;
		for(int iPos = 1; iPos <= nbStatue; iPos++)
		{
			for(int iDeb = 0; iDeb < iPos; iDeb++)
			{
				if((curNb | (cumul[iPos] - cumul[iDeb])) < maxi)
				{
					dp[curBit][iPos] = min(dp[curBit][iPos], dp[curBit][iDeb] + 1);
				}
			}
		}
		if(dp[curBit][nbStatue] <= maxBar)
		{
			return false;
		}
		return true;
	}
	else
	{
		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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...