Submission #948088

#	Time	Username	Problem	Language	Result	Execution time	Memory
948088		pcc	Split the sequence (APIO14_sequence)	C++17	100 / 100	925 ms	127432 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;
const int B = 75;
ll N,K;
pair<ll,int> dp[B+2][mxn];
pair<ll,int> save[6][mxn];
ll pref[mxn];
ll S;

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

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

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];
	int now = 0;
	vector<int> cut = {0};
	int pt = 0;
	for(int i = 1;i<=K+1;i++){
		now++;
		run(now);
		cut.back() = now;
		if(now%B == 0){
			cut.push_back(0);
			pt++;
			for(int j = 0;j<=N;j++){
				dp[0][j] = dp[now][j];
				save[pt][j] = dp[now][j];
			}
			now = 0;
		}
	}
	int pos = N;
	ll val = dp[now][pos].fs;
	vector<int> v;
	while(!cut.empty()){
		for(int i = 0;i<=N;i++){
			dp[0][i] = save[cut.size()-1][i];
		}
		for(int i = 1;i<=cut.back();i++)run(i);
		int now = cut.back();
		while(now>0){
			v.push_back(dp[now][pos].sc);
			pos = dp[now][pos].sc;
			now--;
		}
		cut.pop_back();
	}
	//for(auto &i:v)cout<<i<<',';cout<<endl;
	v.pop_back();
	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:102:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  102 |  assert(v.size() == K);
      |         ~~~~~~~~~^~~~
sequence.cpp:112:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  112 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |  ^~~
sequence.cpp:112:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  112 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |                             ^~~~

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