Submission #244098

#	Time	Username	Problem	Language	Result	Execution time	Memory
244098		GREGOIRELC	Split the sequence (APIO14_sequence)	C++14	49 / 100	194 ms	131076 KiB

sequence

#include <iostream>
#include <deque>

using namespace std;

#define int long long

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

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

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

int find_Coupe(int pos1, int val1, int pos2, int val2)
{
	int deb = pos2, fin = nbInt;
	while(deb < fin - 1)
	{
		int 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(int pos, int coupe, int val)
{
	while(!enCours[coupe].empty())
	{
		int 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(int iNb = 1; iNb <= nbInt; iNb++)
	{
		cin >> valeurs[iNb];
		cumul[iNb] += valeurs[iNb];
		cumul[iNb] += cumul[iNb - 1];
	}
	enCours[0].push_back({0, 0, 0, nbInt});
	int result = 0;
	int dep = 0;
	for(int iPos = 1; iPos <= nbInt; iPos++)
	{
		for(int iCoupe = 1; iCoupe <= nbCoupe; iCoupe++)
		{
			while(enCours[iCoupe - 1].front().fin < iPos)
			{
				enCours[iCoupe - 1].pop_front();
			}
			int pos = enCours[iCoupe - 1].front().pos, val = enCours[iCoupe - 1].front().val;
			dp[iPos][iCoupe] = val + (cumul[iPos] - cumul[pos]) * (cumul[nbInt] - cumul[iPos]);
			//cout << iPos << " " << iCoupe << " " << dp[iPos][iCoupe] << " " << pos << endl;
			origine[iPos][iCoupe] = pos;
			ajoute(iPos, iCoupe, dp[iPos][iCoupe]);
		}
		if(dp[iPos][nbCoupe] > result)
		{
			result = dp[iPos][nbCoupe];
			dep = iPos;
		}
	}
	cout << result << endl;
	int posCoupe = nbCoupe;
	while(posCoupe > 0)
	{
		cout << dep << " ";
		dep = origine[dep][posCoupe];
		posCoupe--;
	}
	cout << endl;
}

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