Submission #101352

#	Time	Username	Problem	Language	Result	Execution time	Memory
101352		DystoriaX	Split the sequence (APIO14_sequence)	C++14	71 / 100	2035 ms	87028 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);
	}
};

deque<Line> ch;
int n, k;
int a[100010];
long long pref[100010];
pair<long long, int> 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(!ch.empty()){
		if(ch.back().m == l.m && ch.back().c > l.c) return;
		if(ch.back().m == l.m) ch.pop_back();
	}

	while(ch.size() >= 2 && !cmp(l, ch.back(), ch[ch.size() - 2])) ch.pop_back();
	ch.push_back(l);
}

pair<long long, int> findOpt(long long x){
	while(ch.size() >= 2 && ch[0].getY(x) <= ch[1].getY(x)) ch.pop_front();

	return {ch[0].getY(x), ch[0].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].first = pref[i] * (pref[n] - pref[i]);
		dp[i].second = 0;
		//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++){
		ch.clear();

		add(Line({pref[j - 1], dp[j - 1].first - pref[j - 1] * pref[n], j - 1}));
		for(int i = j; i < n; i++){
			long long temp = dp[i].first;
			dp[i] = findOpt(pref[i]);
			dp[i].first += pref[i] * (pref[n] - pref[i]);
			bt[i][j] = dp[i].second;
			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].first){
			mx = dp[i].first;
			id = i;
		}
	}

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

	printf("\n");

	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:54: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:57: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