Submission #26039

#	Time	Username	Problem	Language	Result	Execution time	Memory
26039		nibnalin	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	89524 KiB

sequence

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long int lli;
typedef long double dbl;

const lli maxn = lli(1e5)+5, maxk = 205;

int A[maxn], dp2[maxn][maxk];
lli p[maxn], dp[maxn][2];

struct line {
	int id;
	dbl m, c;
	line(dbl _m = 0.00, dbl _c = 0.00, int _id = -1)
	{
		m = _m, c = _c, id = _id;
	}
};

struct CHT {
	int sz = 0;
	line st[maxn];

	inline dbl intersect(line a, line b)
	{
		return (b.c-a.c)/(a.m-b.m);
	}

	void clr()
	{
		sz = 0;
	}

	void insert(line a)
	{
		while(sz > 1)
		{
			if(intersect(st[sz-1], a) <= intersect(st[sz-2], st[sz-1])) sz--;
			else if(st[sz-1].m == a.m) sz--;
			else break;
		}
		st[sz++] = a;
	}

	pair<lli, int> qry(lli x)
	{
		if(!sz) return {0, -1};
		int L = 0, R = sz-1;
		while(L < R)
		{
			int mid = (L+R)/2;
			if(intersect(st[mid], st[mid+1]) <= x) L = mid+1;
			else R = mid;
		}
		return {lli(st[L].m*x+st[L].c), st[L].id};
	}
} C;

int main(void)
{
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i = 1;i <= n;i++) scanf("%d", &A[i]);

	for(int i = 1;i <= n;i++) p[i] = lli(A[i])+p[i-1];

	for(int i = 0;i <= n;i++) dp[i][0] = 0, dp2[i][0] = -1;

	for(int kk = 1;kk <= k;kk++)
	{
		C.clr();
		for(int i = 1;i <= n;i++)
		{
			pair<lli, int> tmp = C.qry(p[i]);
			dp[i][kk] = tmp.first, dp2[i][kk] = tmp.second;
			C.insert({dbl(p[i]), dbl(dp[i][kk-1]-p[i]*p[i]), i});
		}
	}
	printf("%lld\n", dp[n][k]);

	int idx = n;
	for(int kk = k;kk > 0;kk--)
	{
		//if(dp[idx][kk].second == -1) break;
		printf("%d ", dp2[idx][kk]);
		idx = dp2[idx][kk];
	}
	printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:65:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:66:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
                                              ^

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