Submission #101354

#	Time	Username	Problem	Language	Result	Execution time	Memory
101354		DystoriaX	Split the sequence (APIO14_sequence)	C++14	71 / 100	2063 ms	86776 KiB

sequence

#include <bits/stdc++.h>

#define ld long double

using namespace std;

struct Line{
	long long m, c;
	int idx;

	long long getY(long long x){
		return m * x + c;
	}

	ld getX(Line o){
		return (ld) (o.c - c) / (ld) (m - o.m);
	}
};

Line ch[100010];
int sz = 0, opt = 0;
int n, k;
int a[100010];
long long pref[100010];
long long dp[100010];
int bt[100010][210];

bool cmp(Line a, Line b, Line c){
	return a.getX(b) > a.getX(c);
}

void add(Line l){
	if(sz > 0){
		if(ch[sz - 1].m == l.m && ch[sz - 1].c > l.c) return;
		if(ch[sz - 1].m == l.m) sz--;
	}

	while(sz >= 2 && !cmp(l, ch[sz - 1], ch[sz - 2])) sz--;
	ch[sz++] = l;
}

/*pair<long long, int> findOpt(long long x){
	if(opt >= sz) opt = sz - 1;
	
	while(opt + 1 < sz && ch[opt].getY(x) <= ch[opt + 1].getY(x)) opt++;

	return {ch[opt].getY(x), ch[opt].idx};
}*/

void btrack(int i, int j){
	if(i == 0 || j == 0) return;
	btrack(bt[i][j], j - 1);
	printf("%d ", i);
}

int main(){
	scanf("%d%d", &n, &k);

	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		pref[i] = pref[i - 1] + a[i];
	}

	//Base Case, k = 1
	for(int i = 1; i < n; i++){
		dp[i] = pref[i] * (pref[n] - pref[i]);
		//cout << i << " " << 1 << " " << dp[i][1].first << endl;
	}

	// DP formula:
	// dp[i][j] = max(dp[t][j - 1] + cost(t + 1, i) * cost(i + 1, n))
	// for t < i, where cost(i, j) = pref[j] - pref[i - 1]
	// Hence, simplifying the formula gives:
	// dp[i][j] = max(dp[t][j - 1] - pref[t] * pref[n] + pref[t] * pref[i]) + pref[i] * (pref[n] - pref[i])
	// Line equation:
	// m = pref[t]
	// x = pref[i]
	// c = dp[t][j - 1] - pref[t] * pref[n]
	// Note that dp[i][j] is defined for j <= i

	for(int j = 2; j <= k; j++){
		sz = opt = 0;

		add(Line({pref[j - 1], dp[j - 1] - pref[j - 1] * pref[n], j - 1}));
		for(int i = j; i < n; i++){
			long long temp = dp[i], x = pref[i];

			//Query
			if(opt >= sz) opt = sz - 1;
			
			while(opt + 1 < sz && ch[opt].getY(x) <= ch[opt + 1].getY(x)) opt++;

			//Update DP
			dp[i] = ch[opt].getY(x); bt[i][j] = ch[opt].idx;
			dp[i] += pref[i] * (pref[n] - pref[i]);
			add(Line({pref[i], temp - pref[i] * pref[n], i}));
			//cout << i << " " << j << " " << dp[i][j].first << " bt: " << dp[i][j].second <<endl;
		}
	}

	long long mx = -1, id = -1;
	for(int i = k; i < n; i++){
		if(mx < dp[i]){
			mx = dp[i];
			id = i;
		}
	}

	printf("%lld\n", mx);
	btrack(id, k);

	printf("\n");

	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:57:7: 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:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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