Submission #703719

#	Time	Username	Problem	Language	Result	Execution time	Memory
703719		600Mihnea	Split the sequence (APIO14_sequence)	C++17	100 / 100	1353 ms	82540 KiB

sequence

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;

void minup(ll& a, ll b)
{
	a = min(a, b);
}

const int N = 100000 + 7;
const int K = 200 + 7;
const ll INF = (ll)1e18 + 7;
int n;
int k;
ll a[N];
ll pref[N];
ll dp[N];
ll ndp[N];
int par[K][N];

ll get(int l, int r)
{
	return pref[r] - pref[l - 1];
}

void clr()
{
	for (int i = 0; i <= n; i++)
	{
		dp[i] = ndp[i] = INF;
	}
	dp[0] = 0;
}

void swp()
{
	for (int i = 0; i <= n; i++)
	{
		dp[i] = ndp[i];
		ndp[i] = INF;
	}
}

ll co(int i, int j)
{
	if (j <= i)
	{
		return dp[j - 1] + get(j, i) * get(j, i);
	}
	else
	{
		return INF;
	}
}

void dnc(int step, int l, int r, int low, int high)
{
	if (l > r)
	{
		return;
	}
	int i = (l + r) / 2;
	for (int j = low; j <= high; j++)
	{
		ll cur = co(i, j);
		if (cur < ndp[i])
		{
			ndp[i] = cur;
			par[step][i] = j - 1;
		}
	}
	dnc(step, l, i - 1, low, par[step][i] + 1);
	dnc(step, i + 1, r, par[step][i] + 1, high);
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> n >> k;
	k++;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	clr();

	for (int step = 1; step <= k; step++)
	{
		dnc(step, 1, n, 1, n);
		swp();
	}
	ll sol = (get(1, n) * get(1, n) - dp[n]) / 2;
	cout << sol << "\n";
	int p = n;
	for (int step = k; step >= 2; step--)
	{
		cout << par[step][p] << " ";
		p = par[step][p];
	}
	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