Submission #569833

#	Time	Username	Problem	Language	Result	Execution time	Memory
569833		beaconmc	수열 (APIO14_sequence)	C++14	0 / 100	1083 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[100002][202];
ll ans[100002][202];



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


	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+1){
			ll c = 1;
			while (i+c<=n){
				if (dp[i+c][j+1] < dp[i][j] + (suff[i] - suff[i+c])*suff[i+c]){
					ans[i+c][j+1] = i;

					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]);
		}
	}

	FOR(i,0,n+1){
		FOR(j,0,k+1){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	cout << dp[n][k] << endl;
	ll sus = n;

	FOR(i,0,k){
		sus = ans[sus][k-i+1];
		cout << sus-1 << " ";
	}



}

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