제출 #110865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110865		aleksam	수열 (APIO14_sequence)	C++14	0 / 100	19 ms	5376 KiB

sequence

//Apio 14 sequence
#include <bits/stdc++.h>
#define INF INT_MAX
#define MOD 100000007
#define MAX_N 100005
#define MAX_K 205
using namespace std;

int N, K, a[MAX_N];
long long dp[MAX_K][MAX_N];
int sc[MAX_K][MAX_N];

int main(){
	ios::sync_with_stdio(false);
	cin>>N>>K;
	for(int i=0; i<N; ++i){
		cin>>a[i];
	}
	long long s=0;
	for(int i=N-1; i>=0; --i){
		s+=a[i];
		dp[0][i]=s*s;
		sc[0][i]=N;
	}
	for(int k=1; k<=K; ++k){
		s=a[N-k-1];
		dp[k][N-k-1]=dp[k-1][N-k]+s*s;
		sc[k][N-k-1]=N-k;
		int scc=N-k;
		for(int i=N-k-2; i>=0; --i){
			s+=a[i];
			while(scc>i+1 && (s-a[scc-1])*(s-a[scc-1])+dp[k-1][scc-1] < s*s+dp[k-1][scc]){
				scc--;
				s-=a[scc];
			}
			dp[k][i]=s*s+dp[k-1][scc];
			sc[k][i]=scc;
		}
	}
	s=0;
	for(int i=0; i<N; ++i)s+=a[i];
	cout<<(s*s-dp[K][0])/2<<endl;
	int cur=0;
	for(int i=0; i<K; ++i){
		cout<<sc[K-i][cur]<<" ";
		cur=sc[K-i][cur];
	}
	return 0;
}

/*
7 3
4 1 3 4 0 2 3
*/

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