Submission #212754

#	Time	Username	Problem	Language	Result	Execution time	Memory
212754		kig9981	Split the sequence (APIO14_sequence)	C++17	0 / 100	20 ms	3580 KiB

sequence

#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

long long D[2][100001];
int N, PS[100001], P[200][100001];

double cross(int a, int b, int k)
{
	return 1.*(1LL*PS[a]*PS[a]-1LL*PS[b]*PS[b]+D[k&1][b]-D[k&1][a])/(PS[a]-PS[b]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int K, j;
	vector<int> idx;
	cin>>N>>K;
	for(int i=1;i<=N;i++) {
		cin>>PS[i]; PS[i]+=PS[i-1];
	}
	for(int k=1;k<K;k++) {
		idx.clear(); idx.push_back(j=k);
		for(int i=k+1;i<=N;i++) {
			while(j+1<idx.size() && cross(idx[j],idx[j+1],k-1)-1e-9<=PS[i]) j++;
			D[k&1][i]=(PS[i]-PS[idx[j]])*PS[idx[j]]+D[~k&1][idx[j]];
			P[k][i]=idx[j];
			while(idx.size()>1 && cross(idx[idx.size()-2],idx.back(),k-1)>cross(idx.back(),i,k-1)) idx.pop_back();
			idx.push_back(i);
		}
	}
	idx.clear(); j=0;
	for(int i=1;i<N;i++) if(1LL*(PS[N]-PS[i])*PS[i]+D[~K&1][i]>=1LL*(PS[N]-PS[j])*PS[j]+D[~K&1][j]) j=i;
	cout<<1LL*(PS[N]-PS[j])*PS[j]+D[~K&1][j]<<'\n';
	for(int k=K-1;k>=0;k--) {
		idx.push_back(j);
		j=P[k][j];
	}
	reverse(idx.begin(),idx.end());
	for(auto a: idx) cout<<a<<' ';
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j+1<idx.size() && cross(idx[j],idx[j+1],k-1)-1e-9<=PS[i]) j++;
          ~~~^~~~~~~~~~~

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