Submission #221290

#	Time	Username	Problem	Language	Result	Execution time	Memory
221290		cgiosy	Split the sequence (APIO14_sequence)	C++17	0 / 100	134 ms	3932 KiB

sequence

#pragma GCC optimize("O3,fast-math")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct line { ll a, b; int c, i; };
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K;
	cin>>N>>K; K++;
	vector<ll> A(N+1);
	vector<int> P(N+1);
	for(int i=1; i<=N; i++) cin>>A[i], A[i]+=A[i-1];

	vector<line> X(N);
	auto f=[&](ll dt) {
		int n=0, p=0;
		auto f=[&](const line& a, const line& b) {
			return (long double)(a.b-b.b)/(b.a-a.a);
		};
		auto add=[&](line t) {
			if(p<n && X[n-1].a==t.a) {
				if(X[n-1].b>t.b) t=X[n-1];
				n--;
			}
			while(p+1<n && f(X[n-2], X[n-1])>=f(X[n-1], t)) n--;
			X[n++]=t;
		};
		auto get=[&](ll x) {
			while(p+1<n && f(X[p], X[p+1])<=x) p++;
			return X[p];
		};
		add({0, 0, 0, 0});
		for(int i=1; i<=N; i++) {
			auto[a,b,c,k]=get(A[i]);
			P[i]=k;
			add({2*A[i], a*(A[i]-A[k]) - A[i]*A[i] + b - dt, c+1, i});
		}
		return X[n-1].c;
	};
	auto go=[&](const vector<int>& Q) {
		ll x=0;
		for(int i=1; i<K+1; i++) x+=ll(A[Q[i]]-A[Q[i-1]])*A[Q[i-1]];
		cout<<x<<'\n';
		for(int i=1; i<K; i++) cout<<Q[i]<<' ';
		exit(0);
	};
	auto ga=[&](int k) {
		vector<int> Q(k+1);
		for(int i=N, j=k; i; i=P[i]) Q[j--]=i;
		if(k==K) go(Q);
		return Q;
	};

	ll l=0, r=1e17;
	while(l<r) {
		ll m=(l+r)/2;
		auto k=f(m*2+1);
		if(k>K) l=m+1;
		else if(k<K) r=m;
		else r=m;
	}

	auto L=ga(f(2*r-1));
	auto R=ga(f(2*r+1));
	vector<int> M(K+1);
	for(int i=1, p=0; i<L.size(); i++) {
		M[i-1]=L[i-1];
		while(R[p]<=L[i-1]) p++;
		if(R[p]>=L[i] && i+R.size()-p==K+1) {
			while(p<R.size()) M[i++]=R[p++];
			go(M);
			break;
		}
	}

	cout<<"No\n";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1, p=0; i<L.size(); i++) {
                    ~^~~~~~~~~
sequence.cpp:70:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(R[p]>=L[i] && i+R.size()-p==K+1) {
                    ~~~~~~~~~~~~^~~~~
sequence.cpp:71:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(p<R.size()) M[i++]=R[p++];
          ~^~~~~~~~~

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