Submission #443997

#	Time	Username	Problem	Language	Result	Execution time	Memory
443997		negar_a	Split the sequence (APIO14_sequence)	C++14	100 / 100	1696 ms	82544 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn = 1e5 + 2, maxk = 200 + 3;
ll dp[3][maxn], ps[maxn], a[maxn], inf = 1e18;
int opt[maxk][maxn];

inline ll ch(ll x){
	return x * (x - 1) / (ll)2;
}

void solve(int l, int r, int x, int y, int k){
	if(l + 1 > r){
		return;
	}
	int mid = (l + r) / 2;
	dp[k & 1][mid] = inf;
	for(int i = x; i < min(y, mid); i ++){
		ll val = dp[(k - 1) & 1][i] + ch(ps[mid + 1] - ps[i + 1]);
		if(val < dp[k & 1][mid]){
			dp[k & 1][mid] = val;
			opt[k][mid] = i;
		}
	}
	//cout << mid << " " << k << " : " << dp[k][mid] << endl; 
	solve(l, mid, x, opt[k][mid] + 1, k);
	solve(mid + 1, r, opt[k][mid], y, k);
}

int main(){
	fast_io;
	int n, k;
	cin >> n >> k;
	ll sum = 0;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		ps[i + 1] = ps[i] + a[i];
		sum += a[i];
	}
	for(int i = 0; i < n; i ++){
		dp[1][i] = ch(ps[i + 1]);
		opt[1][i] = -1;
	} 
	for(int i = 2; i <= k + 1; i ++){
		solve(0, n, 0, n, i);
	}
	//cout << "dp : " << dp[k + 1][n - 1] << endl;
	cout << ch(sum) - dp[(k + 1) & 1][n - 1] << endl;
	
	int x = opt[k + 1][n - 1];
	int t = k + 1;
	while(x != -1){
		cout << x + 1 << " ";
		t --;
		x = opt[t][x];
	}
	
	
	return 0;
}	

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