Submission #26018

#	Time	Username	Problem	Language	Result	Execution time	Memory
26018		nibnalin	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	3660 KiB

sequence

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

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

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

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

struct CHT {
	int 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 && intersect(st[sz-1], a) < intersect(st[sz-2], st[sz-1]))
		{
			sz--;
		}
		st[sz++] = a;
	}

	pair<int, int> qry(int x)
	{
		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 {int(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] = A[i]+p[i-1];

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

	for(int kk = 1;kk <= k;kk++)
	{
		C.clr();
		C.insert({double(p[0]), 0, 0});
		for(int 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("%d\n", dp[n][k].first);

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

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:59: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:60: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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29