제출 #57030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57030		Plurm	수열 (APIO14_sequence)	C++17	71 / 100	2060 ms	105468 KiB

sequence

#include <cstdio>
#include <cstring>
#define bad(x,y,z) ((C[y]-C[x])*(M[x]-M[z]) >= (C[z]-C[x])*(M[x]-M[y]))
int a[100005];
long long dpnew[100005];
long long dpold[100005]; // End with i, having j parts;
long long qs[100005];
int par[100005][256];
long long M[100005];
long long C[100005];
int idx[100005];
int prt[100005];
int fastscan(){
	int x = 0;
	int c = getchar();
	while(c < 48 || c >= 58) c = getchar();
	while(c >= 48 && c < 58){
		x *= 10;
		x += c-48;
		c = getchar();
	}
	return x;
}
int ptr;
int csz;
int main(){
	int n,k;
	n = fastscan();
	k = fastscan();
	k++;
	csz++;
	for(int i = 1; i <= n; i++){
		a[i] = fastscan();
		qs[i] = qs[i-1] + (long long)a[i];
		dpold[i] = -1e16;
	}
	for(int j = 1; j <= k; j++){
		if(j > 1){
			M[csz] = qs[j-1];
			C[csz] = dpold[j-1] - qs[j-1]*qs[j-1];
			idx[csz] = j-1;
			csz++;
		}
		int id;
		for(int i = j; i <= n; i++){
			if(ptr >= csz) ptr = csz-1;
			while(ptr < csz-1 && M[ptr+1]*qs[i] + C[ptr+1] > M[ptr]*qs[i] + C[ptr]) ptr++;
			id = ptr;
			par[i][j] = idx[id];
			dpnew[i] = M[id]*qs[i] + C[id];
			while(csz >= 2 && (C[csz-1]-C[csz-2])*(M[csz-2]-qs[i]) >= (dpold[i]-qs[i]*qs[i]-C[csz-2])*(M[csz-2]-M[csz-1])) csz--;
			M[csz] = qs[i];
			C[csz] = dpold[i] - qs[i]*qs[i];
			idx[csz] = i;
			csz++;
		}
		memmove(dpold,dpnew,sizeof(dpold));
		csz = ptr = 0;
	}
	printf("%lld\n",dpold[n]);
	int x = n;
	csz = 0;
	for(int j = k; j > 1; j--){
		x = par[x][j];
		prt[csz++] = x;
	}
	for(int i = 0; i < csz; i++){
		printf("%d ",prt[i]);
	}
}

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