Submission #57048

#	Time	Username	Problem	Language	Result	Execution time	Memory
57048		Plurm	Split the sequence (APIO14_sequence)	C++17	71 / 100	2072 ms	107364 KiB

sequence

#include <cstdio>
#include <cstring>
int a[100005];
long long dp[100005];
long long qs[100005];
int par[100005][256];
struct{
	long long M,C;
	int idx;
} L1[100005], L2[100005];
int prt[100005];
int ptr1,ptr2;
int csz1,csz2;
bool bad(long long Mx,long long Cx,long long My,long long Cy,long long Mz,long long Cz){
	return (Mx-My)*(Cz-Cx) <= (Mx-Mz)*(Cy-Cx);
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	k++;
	csz1++;
	for(int i = 1; i <= n; i++){
		scanf("%d",a+i);
		qs[i] = qs[i-1] + (long long)a[i];
		dp[i] = -1e16;
	}
	for(int j = 1; j <= k; j++){
		csz2 = ptr2 = 0;
		int id;
		for(int i = j; i <= n; i++){
			if(ptr1 >= csz1) ptr1 = csz1-1;
			while(ptr1 < csz1-1 && L1[ptr1+1].M*qs[i] + L1[ptr1+1].C > L1[ptr1].M*qs[i] + L1[ptr1].C) ptr1++;
			par[i][j] = L1[ptr1].idx;
			dp[i] = L1[ptr1].M*qs[i] + L1[ptr1].C;
			while(csz2 >= 2 && bad(L2[csz2-2].M,L2[csz2-2].C,L2[csz2-1].M,L2[csz2-1].C,qs[i],dp[i]-qs[i]*qs[i])) csz2--;
			L2[csz2].M = qs[i];
			L2[csz2].C = dp[i] - qs[i]*qs[i];
			L2[csz2].idx = i;
			csz2++;
		}
		for(int i = 0; i < csz2; i++){
			L1[i] = L2[i];
		}
		csz1 = csz2;
		ptr1 = ptr2;
	}
	printf("%lld\n",dp[n]);
	int x = n;
	csz1 = 0;
	for(int j = k; j > 1; j--){
		x = par[x][j];
		prt[csz1++] = x;
	}
	for(int i = 0; i < csz1; i++){
		printf("%d ",prt[i]);
	}
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:29:7: warning: unused variable 'id' [-Wunused-variable]
   int id;
       ^~
sequence.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+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