Submission #26036

#	Time	Username	Problem	Language	Result	Execution time	Memory
26036		nibnalin	Split the sequence (APIO14_sequence)	C++14	50 / 100	13 ms	5276 KiB

sequence

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

typedef long long int lli;

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

lli A[maxn], p[maxn];
pair<lli, lli> dp[maxn][maxk];

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

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

	inline double 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, lli> qry(lli x)
	{
		if(!sz) return {0, -1};
		lli L = 0, R = sz-1;
		while(L < R)
		{
			lli 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)
{
	lli n, k;
	scanf("%lld%lld", &n, &k);
	for(lli i = 1;i <= n;i++) scanf("%lld", &A[i]);

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

	for(lli i = 0;i <= n;i++) dp[i][0] = {0, -1};

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

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

Compilation message (stderr)

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

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