Submission #43644

#	Time	Username	Problem	Language	Result	Execution time	Memory
43644		sorry_Benq	Split the sequence (APIO14_sequence)	C++14	0 / 100	16 ms	16940 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll S[10005];
ll DP[10005][205];
const ll INF = 1e18;
int pointer; //Keeps track of the best line from previous query
vector<long long> M; //Holds the slopes of the lines in the envelope
vector<long long> B; //Holds the y-intercepts of the lines in the envelope
//Returns true if either line l1 or line l3 is always better than line l2
bool bad(int l1,int l2,int l3)
{
	/*
	intersection(l1,l2) has x-coordinate (b1-b2)/(m2-m1)
	intersection(l1,l3) has x-coordinate (b1-b3)/(m3-m1)
	set the former greater than the latter, and cross-multiply to
	eliminate division
	*/
	return (B[l3]-B[l1])*(M[l1]-M[l2])<(B[l2]-B[l1])*(M[l1]-M[l3]);
}
//Adds a new line (with lowest slope) to the structure
void add(long long m,long long b)
{
	//First, let's add it to the end
	M.push_back(m);
	B.push_back(b);
	//If the penultimate is now made irrelevant between the antepenultimate
	//and the ultimate, remove it. Repeat as many times as necessary
	while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))
	{
		M.erase(M.end()-2);
		B.erase(B.end()-2);
	}
}
//Returns the minimum y-coordinate of any intersection between a given vertical
//line and the lower envelope
long long query(long long x)
{
	//If we removed what was the best line for the previous query, then the
	//newly inserted line is now the best for that query
	if (pointer>=M.size())
		pointer=M.size()-1;
	//Any better line must be to the right, since query values are
	//non-decreasing
	while (pointer<M.size()-1&&
	  M[pointer+1]*x+B[pointer+1]<M[pointer]*x+B[pointer])
		pointer++;
	return M[pointer]*x+B[pointer];
}
int main(){
	S[0] = 0;
	int N, K; cin >> N >> K;
	for (int i = 1; i <= N; i++){
		ll x; cin >> x;
		S[i] = S[i - 1] + x;
	}
	for (int i = 1; i <= N; i++){
		DP[i][1] = S[i]*S[i];
	}
	for (int j = 2; j <= K + 1; j++){
		pointer = 0; M.clear(); B.clear();
		for (int i = j; i <= N; i++){
			add(-2*S[i - 1], DP[i - 1][j - 1] + S[i - 1]*S[i - 1]);
			DP[i][j] = S[i]*S[i] + query(S[i]);
		}
	}
	int curpos = N;
	vector<int> idx; 
	for (int j = K + 1; j >= 2; j--){
		for (int i = curpos - 1; i >= 0; i--){
			if (DP[curpos][j] == DP[i][j - 1] + (S[i] - S[curpos])*(S[i] - S[curpos])){
				idx.push_back(i);
				curpos = i;
				break;
			}
		}
	}
	sort(idx.begin(), idx.end());
	cout << (S[N] * S[N] - DP[N][K + 1])/2 << endl;
	for (int j: idx){
		cout << j << ' ';
	}
	cout << endl;
}

Compilation message (stderr)

sequence.cpp: In function 'long long int query(long long int)':
sequence.cpp:42:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (pointer>=M.size())
             ^
sequence.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (pointer<M.size()-1&&
                ^

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