Submission #244204

#	Time	Username	Problem	Language	Result	Execution time	Memory
244204		GREGOIRELC	Split the sequence (APIO14_sequence)	C++14	60 / 100	2061 ms	84684 KiB

sequence

#include <iostream>
#include <deque>

using namespace std;

const long long MAX_NB = 1e5 + 1;
const long long MAX_COUPE = 200 + 1;

struct Info
{
	long long pos, val, deb, fin;
};

long long nbInt, nbCoupe;
long long valeurs[MAX_NB];
long long cumul[MAX_NB];
long long dp[2][MAX_COUPE];
int origine[MAX_NB][MAX_COUPE];
deque<Info> enCours[MAX_COUPE];

long long find_Coupe(long long pos1, long long val1, long long pos2, long long val2)
{
	long long deb = pos2, fin = nbInt;
	while(deb < fin - 1)
	{
		long long mid = (deb + fin) / 2;
		if(val1 + (cumul[mid] - cumul[pos1]) * (cumul[nbInt] - cumul[mid]) < val2 + (cumul[mid] - cumul[pos2]) * (cumul[nbInt] - cumul[mid]))
		{
			fin = mid;
		}
		else
		{
			deb = mid;
		}
	}
	if(val1 + (cumul[deb] - cumul[pos1]) * (cumul[nbInt] - cumul[deb]) < val2 + (cumul[deb] - cumul[pos2]) * (cumul[nbInt] - cumul[deb]))
	{
		return deb;
	}
	return fin;
}

void ajoute(long long pos, long long coupe, long long val)
{
	while(!enCours[coupe].empty())
	{
		long long ces = find_Coupe(enCours[coupe].back().pos, enCours[coupe].back().val, pos, val);
		if(ces - 1 < enCours[coupe].back().deb)
		{
			enCours[coupe].pop_back();
		}
		else
		{
			enCours[coupe].back().fin = ces - 1;
			break;
		}
	}
	if(enCours[coupe].empty())
	{
		enCours[coupe].push_back({pos, val, 0, nbInt});
	}
	else
	{
		enCours[coupe].push_back({pos, val, enCours[coupe].back().fin + 1, nbInt});
	}
}

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

	cin >> nbInt >> nbCoupe;
	for(long long iNb = 1; iNb <= nbInt; iNb++)
	{
		cin >> valeurs[iNb];
		cumul[iNb] += valeurs[iNb];
		cumul[iNb] += cumul[iNb - 1];
	}
	if(nbInt == 2)
	{
		cout << 1 << endl;
		cout << valeurs[1] * valeurs[2] << endl;
		return 0;
	}
	enCours[0].push_back({0, 0, 0, nbInt});
	long long result = 0;
	long long dep = 0;
	for(long long iPos = 1; iPos <= nbInt; iPos++)
	{
		for(long long iCoupe = nbCoupe; iCoupe >= 1; iCoupe--)
		{
			if(enCours[iCoupe - 1].empty())
			{
				continue;
			}
			while(enCours[iCoupe - 1].front().fin < iPos)
			{
				enCours[iCoupe - 1].pop_front();
			}
			long long pos = enCours[iCoupe - 1].front().pos, val = enCours[iCoupe - 1].front().val;
			dp[iPos % 2][iCoupe] = val + (cumul[iPos] - cumul[pos]) * (cumul[nbInt] - cumul[iPos]);
			origine[iPos][iCoupe] = pos;
			ajoute(iPos, iCoupe, dp[iPos % 2][iCoupe]);
		}
		if(dp[iPos % 2][nbCoupe] > result)
		{
			result = dp[iPos % 2][nbCoupe];
			dep = iPos;
		}
	}
	cout << result << endl;
	long long posCoupe = nbCoupe;
	while(posCoupe > 0)
	{
		cout << dep << " ";
		dep = origine[dep][posCoupe];
		posCoupe--;
	}
	cout << endl;
}

• Subtask 1: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29