Submission #948053

#	Time	Username	Problem	Language	Result	Execution time	Memory
948053		pcc	Split the sequence (APIO14_sequence)	C++17	11 / 100	95 ms	6020 KiB

sequence

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+2;
ll N,K;
pair<pll,int> dp[mxn];
ll pref[mxn];
ll S;

struct line{
	int id,cnt;
	ll m,b;
	pll operator()(ll k){
		return pll(m*k+b,cnt+1);
	}
	line(){}
	line(ll a,ll bb,int ii,int cc){
		m = a,b = bb;
		id = ii;
		cnt = cc;
	}
};

deque<line> dq;

bool btw(line a,line b,line c){
	if(b.m == c.m&&b.b<c.b)return true;
	if(a.m == b.m&&a.b>b.b)return true;
	return (a.b-b.b)*(c.m-b.m)>(b.b-c.b)*(b.m-a.m);
}

pll run(ll tax){
	while(!dq.empty())dq.pop_back();
	line tt = line(0ll,0ll,0,0);
	dq.push_back(tt);
	for(int i = 1;i<=N;i++){
		while(dq.size()>1&&dq[0](pref[i])<=dq[1](pref[i]))dq.pop_front();
		dp[i].fs.fs = dq[0](pref[i]).fs+S*pref[i]-pref[i]*pref[i]-tax;
		dp[i].fs.sc = dq[0](pref[i]).sc;
		dp[i].sc = dq[0].id;
		line tmp = line(pref[i]*2,dp[i].fs.fs-pref[i]*pref[i]-S*pref[i],i,dp[i].fs.sc);
		while(dq.size()>1&&btw(dq.end()[-2],dq.end()[-1],tmp))dq.pop_back();
		dq.push_back(tmp);
	}
	return dp[N].fs;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++){
		cin>>pref[i];
		pref[i] += pref[i-1];
	}
	S = pref[N];
	ll l = -1e13,r = 1e13;
	while(l != r){
		ll mid = l+(r-l+1)/2;
		auto re = run(mid);
		//cout<<mid<<":"<<re.fs<<','<<re.sc<<endl;
		if(re.sc<K+1)r = mid-1;
		else l = mid;
	}
	run(l);
	int pos = N;
	ll val = dp[N].fs.fs+(K+1)*l;
	vector<int> v;
	for(int i = K+1;i>1;i--){
		pos = dp[pos].sc;
		v.push_back(pos);
	}
	assert(v.size() == K);

	/*
	cout<<S<<endl;
	for(int i = 0;i<=K;i++){
		for(int j = 0;j<=N;j++)cout<<dp[i][j].fs<<' '<<dp[i][j].sc<<',';cout<<endl;
	}
   */

	cout<<val/2<<'\n';
	for(auto &i:v)cout<<i<<' ';cout<<'\n';
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp: In function 'int main()':
sequence.cpp:83:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   83 |  assert(v.size() == K);
      |         ~~~~~~~~~^~~~
sequence.cpp:93:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   93 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |  ^~~
sequence.cpp:93:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   93 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |                             ^~~~

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