Submission #310146

#	Time	Username	Problem	Language	Result	Execution time	Memory
310146		sofapuden	Split the sequence (APIO14_sequence)	C++14	89 / 100	1741 ms	83064 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int v[100005];
ll dp[2][100005];
int L[100005][205];
int k;

void find(int l, int r, int lb, int rb, int Z){
	if(l > r)return;
	int mid = (l+r)>>1;
	
	int pos = lb; ll ma = -1;
	for(int i = lb; i < min(mid,rb+1); ++i){
		if(ma < 1ll * dp[0][i]+ 1ll * (v[mid]-v[i])*v[i]){
			ma = 1ll * dp[0][i]+ 1ll * (v[mid]-v[i])*v[i];
			pos = i;
		}
	}
	dp[1][mid] = ma;
	L[mid][Z] = pos;
	find(l,mid-1,lb,pos,Z);
	find(mid+1,r,pos,rb,Z);
}
	

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n >> k;
	for(int i = 1; i <= n; ++i){
		cin >> v[i];
	}
	for(int i = 1; i <= n; ++i){
		v[i]+=v[i-1];
	}
	ll ans = 0, ind = 0;
	for(int i = 1; i<=k; ++i){
		find(1,n,1,n,i);
		for(int j = 1; j <= n; ++j)dp[0][j] = dp[1][j];
	}
	for(int i = 1; i <= n; ++i){
		if(ans < dp[0][i]){
			ind = i;
			ans = dp[0][i];
		}
	}
	cout << ans << "\n";
	
	while(k--){
		cout << L[ind][k+1] << " ";
		ind = L[ind][k+1];
	}
	cout << "\n";
}
	
		
	

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