Submission #101683

#	Time	Username	Problem	Language	Result	Execution time	Memory
101683		DystoriaX	Split the sequence (APIO14_sequence)	C++14	100 / 100	642 ms	83444 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];
pair<long long, int> dp[100010];
int bt[210][100010];
 
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[j][i], 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++){
		sz = opt = 0;
 
		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[j][i] = 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: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: 29 / 29