Submission #977962

#	Time	Username	Problem	Language	Result	Execution time	Memory
977962		raspy	Split the sequence (APIO14_sequence)	C++14	100 / 100	676 ms	84340 KiB

sequence

#include <iostream>
#include <vector>
#include <deque>

#define int long long

using namespace std;

struct ln
{
	int m;
	int c;
	int num;
	ln(int _m, int _c, int _nm) : m(_m), c(_c), num(_nm) {}
	friend double presek(const ln l1, const ln l2) { return (double)(l2.c - l1.c) / (double)(l1.m - l2.m); }
	int operator()(int x) { return m*x + c; };
};

int km[100005];
int32_t par[205][100005];
vector<int> dp(100005);
vector<int> ndp(100005);
deque<ln> dq;

int32_t main()
{
	cin.tie(NULL);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> km[i];
		km[i] += km[i-1];
	}
	for (int i = 1; i <= k+1; i++)
	{
		dq.clear();
		for (int j = 1; j <= n; j++)
		{
			ln tr(km[j-1], dp[j-1]-km[n]*km[j-1], j-1);
			while (dq.size() >= 2 && presek(tr, dq[dq.size()-1]) <= presek(dq[dq.size()-2], tr))
				dq.pop_back();
			dq.push_back(tr);
			while (dq.size() >= 2 && dq[0](km[j]) <= dq[1](km[j]))
				dq.pop_front();
			ndp[j] = dq[0](km[j]) + km[j]*km[n]-km[j]*km[j];
			par[i][j] = dq[0].num;
		}
		dp = ndp;
	}
	cout << dp[n] << '\n';
	int32_t tr = n;
	for (int i = k+1; i > 1; i--)
	{
		tr = par[i][tr];
		cout << tr << " ";
	}
	cout << "\n";
	return 0;
}

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