제출 #569788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569788		beaconmc	Split the sequence (APIO14_sequence)	C++14	0 / 100	588 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

ll dp[100001][200];



int main(){
	ll n,k;
	cin >> n >> k;
	k += 1;

	ll suff[n+1];

	vector<ll> nums(n);
	FOR(i,0,n) cin >> nums[i];

	suff[n] = 0;
	suff[n-1] = nums[n-1];
	FORNEG(i,n-2,-1){
		suff[i] = suff[i+1] + nums[i];
	}


	dp[0][0] = 0;
	FOR(i,0,n){
		FOR(j,0,k){
			ll c = 1;
			while (i+c<=n) dp[i+c][j+1] = max(dp[i+c][j+1], dp[i][j] + (suff[i] - suff[i+c])*suff[i+c]), c++;
			dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
		}
	}
	cout << dp[n][k];




}

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