Submission #1050956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050956		modwwe	Split the sequence (APIO14_sequence)	C++17	100 / 100	48 ms	4448 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+1);
	auto f=[&](ll dt) {
		int n=0, p=0;
		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 && __int128(X[n-2].b-X[n-1].b)*(t.a-X[n-1].a)>=__int128(X[n-1].b-t.b)*(X[n-1].a-X[n-2].a)) n--;
			X[n++]=t;
		};
		auto get=[&](ll x) {
			while(p+1<n && X[p].b-X[p+1].b<=x*(X[p+1].a-X[p].a)) p++;
			return X[p];
		};
		add({0, 0, 0, 0});
		for(int i=1; i<=N; i++) {
			auto[a,b,c,k]=get(2*(A[i]-A[N]));
			P[i]=k;
			add({A[i], a*2*(A[i]-A[N]) + 2*(A[N]-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 ga(k), 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:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=1, p=0; i<L.size(); i++) {
      |                    ~^~~~~~~~~
sequence.cpp:67:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |   if(R[p]>=L[i] && i+R.size()-p==K+1) {
      |                    ~~~~~~~~~~~~^~~~~
sequence.cpp:68:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    while(p<R.size()) M[i++]=R[p++];
      |          ~^~~~~~~~~

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