제출 #1326379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326379		SSKMF	수열 (APIO14_sequence)	C++20	71 / 100	117 ms	196608 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

int64_t prefix[100001] , maxim[100001][202];
int sursa[100001][202];

inline void Divide (const int actual , const int inceput , const int sfarsit , const int stanga , const int dreapta)
{
	if (inceput > sfarsit)
		{ return; }

	const int indice = (inceput + sfarsit) >> 1;
	pair <int64_t , int> optim = {INT64_MIN , -1};
	for (int __indice = stanga ; __indice <= min(dreapta , indice - 1) ; __indice++)
		{ optim = max(optim , {maxim[__indice][actual - 1] + (prefix[indice] - prefix[__indice]) * prefix[__indice] , __indice}); }

	Divide(actual , inceput , indice - 1 , stanga , optim.second);
	Divide(actual , indice + 1 , sfarsit , optim.second , dreapta);
	sursa[indice][actual] = optim.second;
	maxim[indice][actual] = optim.first;
}

int main ()
{
	ios :: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int lungime , dorit;
	cin >> lungime >> dorit;

	for (int indice = 1 ; indice <= lungime ; indice++)
		{ cin >> prefix[indice]; prefix[indice] += prefix[indice - 1]; }

	dorit++;
	for (int indice = 2 ; indice <= dorit ; indice++)
		{ Divide(indice , indice , lungime , indice - 1 , lungime - 1); }

	cout << maxim[lungime][dorit] << '\n';

	int stiva[202] = { };
	for (int capat = lungime , indice = dorit ; sursa[capat][indice] ; capat = sursa[capat][indice--])
		{ stiva[++stiva[0]] = sursa[capat][indice]; }

	while (stiva[0])
		{ cout << stiva[stiva[0]--] << ' '; }

	return 0;
}

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