Submission #259160

#	Time	Username	Problem	Language	Result	Execution time	Memory
259160		pure_mem	Split the sequence (APIO14_sequence)	C++14	100 / 100	1408 ms	81496 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int N = 1e5 + 12;

int n, k, T, IT;
int gr[220][N];
ll pr[N], dp[2][N];

void rec(int tl, int tr, int tpl = 1, int tpr = n){
	if(tl > tr)
		return;
	int tm = (tl + tr) / 2, tp = 0;
	ll curs = -1;
	for(int i = max(tpl, IT - 1);i <= min(tm - 1, tpr);i++){
		if(dp[1 - T][i] + pr[i] * (pr[tm] - pr[i]) > curs)	
			curs = dp[1 - T][i] + pr[i] * (pr[tm] - pr[i]), tp = i;	
	}
	dp[T][tm] = curs, gr[IT][tm] = tp;
	rec(tl, tm - 1, tpl, tp);
	rec(tm + 1, tr, tp, tpr);
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
    	cin >> pr[i];
    	pr[i] += pr[i - 1];
    }
    k += 1;
    for(int i = 2;i <= k;i++){
    	T = i & 1, IT = i;
    	rec(1, n);	
    }
    cout << dp[k & 1][n] << "\n";
    for(int j = k, pos = n;j > 1;j--){
    	cout << gr[j][pos] << " ";
    	pos = gr[j][pos];	
    }
}

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