제출 #94688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94688		davitmarg	Split the sequence (APIO14_sequence)	C++17	28 / 100	2055 ms	129572 KiB

sequence

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n, k;
LL a[100005], pr[100005], dp[2][100005];
int nxt[202][100005];
LL sum(int l, int r)
{
	return pr[r] - pr[l - 1];
}

struct line
{
	int i;
	LL k, b;
	line(LL kk = 0, LL bb = 0, int ii = 0)
	{
		k = kk;
		b = bb;
		i = ii;
	}
};

LL f(line g, LL x)
{
	return g.k*x + g.b;
}

line maxLine(line a,line b,LL x)
{
	if (a.k*x + a.b >= b.k*x + b.b)
		return a;
	return b;
}

vector<line> t;
vector<int> lson, rson;

void update(int v,LL l,LL r,line nw)
{
	LL m = (l + r) / 2;
	bool lef = f(t[v], l) < f(nw, l);
	bool mid = f(t[v], m) < f(nw, m);
	if (mid)
		swap(nw, t[v]);
	if (r - l == 0)
		return;
	else if (lef != mid)
	{
		if (lson[v] == -1)
		{
			lson[v] = t.size();
			t.PB(line(0,-mod*mod));
			lson.PB(-1);
			rson.PB(-1);
		}
		update(lson[v],l,m,nw);
	}
	else
	{
		if (rson[v] == -1)
		{
			rson[v] = t.size();
			t.PB(line(0, -mod * mod));
			lson.PB(-1);
			rson.PB(-1);
		}
		update(rson[v], m+1, r, nw);
	}
}

line get(int v,LL l,LL r,LL x)
{
	if (l == r)
		return t[v];
	LL m = (l + r) / 2;
	if (x <= m)
	{
		if (lson[v] == -1)
		{
			lson[v] = t.size();
			t.PB(line(0, -mod * mod));
			lson.PB(-1);
			rson.PB(-1);
		}
		return maxLine(t[v], get(lson[v],l,m,x),x);
	}
	else
	{
		if (rson[v] == -1)
		{
			rson[v] = t.size();
			t.PB(line(0, -mod * mod));
			lson.PB(-1);
			rson.PB(-1);
		}
		return maxLine(t[v], get(rson[v], m + 1, r, x), x);
	}
}

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

	for (int z = 1; z <= k; z++)
	{
		int i = z % 2;
		int l = !i;

		t.resize(0);
		lson.resize(0);
		rson.resize(0);

		t.PB(line(0,-mod*mod));
		lson.PB(-1);
		rson.PB(-1);

		for (int j = n; j >= 1; j--)
		{
			line add = line(pr[j], dp[l][j + 1] - pr[j] * pr[j], j);
			update(0,0,2*mod,add);
			LL X = pr[n] + pr[j - 1];
			line best = get(0,0,2*mod,X);
			dp[i][j] = best.k*X + best.b - pr[j - 1] * pr[n];
			nxt[z][j] = best.i;
		}
	}

	cout << dp[k % 2][1] << endl;
	for (int i = k, l = 1; i >= 1; i--)
	{
		cout << nxt[i][l] << " ";
		l = nxt[i][l] + 1;
	}
	cout << endl;
	return 0;
}

/*


3 1
2 1 2


40 3
7 5 7 5 1 2 3 4 6 7 8 2 1 2 3 4 6 7 8 2 7 7 5 1 2 3 4 6 7 8 2 5 1 2 3 4 6 7 8 2

7 3
4 1 3 4 0 2 3


*/

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