Submission #43639

#	Time	Username	Problem	Language	Result	Execution time	Memory
43639		sorry_Benq	Split the sequence (APIO14_sequence)	C++14	0 / 100	1 ms	488 KiB

sequence

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

ll S[100005];
ll DP[100005][205];
const ll INF = 1e18;

int main(){
	S[0] = 0;
	int N, K; cin >> N >> K;
	for (int i = 1; i <= N; i++){
		ll x; cin >> x;
		S[i] = S[i - 1] + x;
	}
	for (int i = 1; i <= N; i++){
		DP[i][1] = S[i]*S[i];
	}
	for (int j = 2; j <= K + 1; j++){
		for (int i = j; i <= N; i++){
			DP[i][j] = INF;
			for (int r = j - 1; r < i; r++){
				DP[i][j] = min(DP[i][j], (S[i] - S[r]) * (S[i] - S[r]) + DP[r][j - 1]);
			}
		}
	}
	
	cout << (S[N] * S[N] - DP[N][K + 1])/2 << endl;
}

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