Submission #736409

#	Time	Username	Problem	Language	Result	Execution time	Memory
736409		Abrar_Al_Samit	Split the sequence (APIO14_sequence)	C++17	33 / 100	390 ms	4052 KiB

sequence

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

const int nax = 1005;
const long long INF = 1e18;

int n, k;
long long dp[nax][203];
long long a[nax], to[nax][203];
vector<int>config;

long long solve(int i, int j) {
	if(i>n) {
		if(j==k+2) return 0;
		return INF;
	}
	long long &ret = dp[i][j];
	if(ret!=-1) return ret;

	ret = INF;
	long long cur = 0, sub = 0;
	for(int p=i; p<=n; ++p) {
		cur += a[p];
		sub += a[p] * a[p];

		long long cand = cur * cur - sub + solve(p+1, j+1);
		if(cand < ret) {
			ret = cand;
			to[i][j] = p;
		}
	}
	return ret;
}
void construct(int i, int j) {
	if(i>n) return;
	if(to[i][j]<n) config.push_back(to[i][j]);
	construct(to[i][j]+1, j+1);
}
void PlayGround() {
	cin>>n>>k;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}

	long long S = accumulate(a+1, a+n+1, 0LL);

	long long base = 0;
	for(int i=1; i<=n; ++i) {
		base += (S-a[i]) * a[i];
	}

	memset(dp, -1, sizeof dp);
	cout<<(base - solve(1, 1)) / 2<<'\n';
	construct(1, 1);
	for(int x : config) {
		cout<<x<<' ';
	}
	cout<<'\n';

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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