Submission #57011

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

sequence

#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define bad(x,y,z) ((C[y]-C[x])*(M[x]-M[z]) >= (C[z]-C[x])*(M[x]-M[y]))
using namespace std;
int a[100005];
long long dp[100005][2]; // End with i, having j parts;
long long qs[100005];
int par[100005][256];
vector<int> M;
vector<long long> C;
vector<int> idx;
int ptr;
inline 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 main(){
	int n,k;
	n = fastscan();
	k = fastscan();
	k++;
	M.push_back(0);
	C.push_back(0);
	idx.push_back(0);
	for(int i = 1; i <= n; i++){
		a[i] = fastscan();
		qs[i] = qs[i-1] + (long long)a[i];
		dp[i][0] = -1e16;
	}
	for(int j = 1; j <= k; j++){
		if(j > 1){
			M.push_back(qs[j-1]);
			C.push_back(dp[j-1][(j+1) % 2] - qs[j-1]*qs[j-1]);
			idx.push_back(j-1);
			while(M.size() >= 3 && bad(M.size()-3, M.size()-2, M.size()-1)){
				M.erase(M.end()-2);
				C.erase(C.end()-2);
				idx.erase(idx.end()-2);
			}
		}
		for(int i = j; i <= n; i++){
			if(ptr >= M.size()) ptr = M.size()-1;
			while(ptr < M.size()-1 && M[ptr+1]*qs[i] + C[ptr+1] > M[ptr]*qs[i] + C[ptr]) ptr++;
			int id = ptr;
			par[i][j] = idx[id];
			dp[i][j % 2] = M[id]*qs[i] + C[id];
			M.push_back(qs[i]);
			C.push_back(dp[i][(j+1) % 2] - qs[i]*qs[i]);
			idx.push_back(i);
			while(M.size() >= 3 && bad(M.size()-3, M.size()-2, M.size()-1)){
				M.erase(M.end()-2);
				C.erase(C.end()-2);
				idx.erase(idx.end()-2);
			}
		}
		M.clear();
		C.clear();
		idx.clear();
		ptr = 0;
	}
	printf("%lld\n",dp[n][k % 2]);
	int x = n;
	stack<int> stk;
	for(int j = k; j > 1; j--){
		x = par[x][j];
		stk.push(x);
	}
	while(!stk.empty()){
		printf("%d ",stk.top());
		stk.pop();
	}
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:51:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ptr >= M.size()) ptr = M.size()-1;
       ~~~~^~~~~~~~~~~
sequence.cpp:52:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ptr < M.size()-1 && M[ptr+1]*qs[i] + C[ptr+1] > M[ptr]*qs[i] + C[ptr]) ptr++;
          ~~~~^~~~~~~~~~~~

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