Submission #36858

#	Time	Username	Problem	Language	Result	Execution time	Memory
36858		ae04071	Split the sequence (APIO14_sequence)	C++11	0 / 100	0 ms	1008 KiB

sequence

#include <cstdio>
#include <algorithm>
#include <vector>
#include <assert.h>

using namespace std;
typedef long long lli;

int n,k;
lli arr[100001],psum[100001],cache[100001][201],pr[100001][201];
lli a[100001],b[100001];
int pi[100001],sz,si;

vector<int> res;

bool inter() {
	lli le = (b[sz-1]-b[sz-2])*(a[sz-1]-a[sz]);
	lli ri = (b[sz]-b[sz-1])*(a[sz-2]-a[sz-1]);
	return le>=ri;
}
void push(int i,int j) {
	if(sz!=0 && a[sz-1]==psum[i]) {
		lli bb=cache[i][j] - psum[i] * psum[i];
		if(bb>b[sz-1]) {
			b[sz-1] = bb;
			pi[sz-1] = i;
		}
		return;
	}

	a[sz] = psum[i]; b[sz] = cache[i][j] - psum[i] * psum[i];
	pi[sz] = i;
	while(sz-2>=si) {
		if(!inter()) break;
		a[sz-1] = a[sz]; b[sz-1] = b[sz]; pi[sz-1] = pi[sz];
		sz--;
	}
	sz++;
}
void comp(int i) {
	while(si+1<sz) {
		lli lv = a[si]*psum[i] + b[si];
		lli rv = a[si+1]*psum[i] + b[si+1];
		if(lv<=rv) si++;
		else break;
	}
}
void trace(int i,int j) {
	if(j==0) return;
	else {
		trace(pr[i][j],j-1);
		res.push_back(pr[i][j]);
	}
}
int main() {
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%lld",arr+i);
		psum[i]=psum[i-1]+arr[i];
	}

	for(int t=1;t<=k;t++) {
		sz=si=0;
		push(t,t-1);
		for(int i=t+1;i<=n;i++) {
			comp(i);
			cache[i][t] = a[si]*psum[i] + b[si];
			pr[i][t] = pi[si];
			push(i,t-1);
		}
	}

	printf("%lld\n",cache[n][k]);
	trace(n,k);
	for(int i=0;i<res.size();i++) printf("%d ",res[i]);
	
	sort(res.begin(),res.end());
	res.erase(unique(res.begin(),res.end()),res.end());
	assert((int)res.size() == k);
	
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<res.size();i++) printf("%d ",res[i]);
               ^
sequence.cpp:56:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
sequence.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",arr+i);
                      ^

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