제출 #5778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5778		gs12037	수열 (APIO14_sequence)	C++98	0 / 100	0 ms	131072 KiB

sequence

#include <stdio.h>
#include <algorithm>
#define M 100009
using namespace std;

int n, k,path[200][M];
long long int d[209][M],ans,s[M];

long long int f(int i, int j, int r){
	return d[i][r] + (s[n] - s[j])*(s[j] - s[r]);
}
int main(){
	int i, j;
	scanf("%d %d", &n, &k);
	for (i = 1; i <= n; i++) scanf("%d", &s[i]);
	for (i = 1; i <= n; i++) s[i] = s[i - 1] + s[i];

	int pivot;
	for (i = 1; i <= k; i++){
		pivot = 0;
		for (j = 1; j <= n; j++){
			while (s[j] >= (s[n] + s[pivot]) / 2 && f(i - 1, j, pivot) <= f(i - 1, j, pivot + 1) && pivot < j) pivot++;
			d[i][j] = f(i - 1, j, pivot);
			path[i][j] = pivot;
		}
	}
	for (i = 1; i <= n; i++) ans = max(ans, d[k][i]);
	for (i = 1; i <= n; i++){
		if (ans == d[k][i]){
			int temp = i;
			for (j = k; j >= 1; j--){
				s[j] = temp;
				temp = path[j][temp];
			}
			break;
		}
	}
	for (j = 1; j <= k; j++) printf("%d ", s[j]);
	printf("\n%d", ans);
}

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