Submission #443225

#	Time	Username	Problem	Language	Result	Execution time	Memory
443225		minoum	Split the sequence (APIO14_sequence)	C++17	71 / 100	2088 ms	75736 KiB

sequence

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e5+5, K = 200+2;

int n, k;
ll dp[2][MAXN], prs[MAXN], s = 0;
int par[K][MAXN];

inline ll getsum(int l, int r){ //[,]
	ll tmp = prs[r] - (l>0?prs[l-1]:0ll);
	return (((tmp-1ll)*tmp)/2ll);
}

void calc(int id, int l, int r, int opl, int opr){ //[l,r)
	if(r-l<1) return;
	int mid = (l+r)/2;
	int op = opl;
	for(int i = opl+1; i <= min(mid-1,opr-1); i++) if(dp[1-(id%2)][i]+getsum(i+1,mid)<dp[1-(id%2)][op]+getsum(op+1,mid)) op = i; 
	dp[id%2][mid] = dp[1-(id%2)][op]+getsum(op+1,mid); par[id][mid] = op;
	calc(id, l, mid, opl, op+1);
	calc(id, mid+1, r, op, opr);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k; k++;
	for(int i = 0; i < n; i++){
		cin >> prs[i];
		prs[i] = prs[i] + (i==0?0ll:prs[i-1]);
	}
	for(int i = 0; i < n; i++) dp[0][i] = getsum(0,i); //getsum: [,]
	for(int i = 1; i < k; i++) calc(i,i,n,i-1,n);
	cout << (getsum(0,n-1)-dp[1-(k%2)][n-1]) << '\n';
	int x = k-1, y = n-1;
	vector <int> vec;
	while(x>0){
		y = par[x][y];
		vec.push_back(y+1);
		x--;
	}
	while(!vec.empty()){
		cout << vec.back() << " ";
		vec.pop_back();
	}
	cout << '\n';
	return 0; 
}

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