Submission #948037

#	Time	Username	Problem	Language	Result	Execution time	Memory
948037		pcc	Split the sequence (APIO14_sequence)	C++17	71 / 100	41 ms	32084 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 = 1e4+10;
ll N,K;
pair<ll,int> dp[202][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){
	dq.clear();
	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];
	for(int i = 1;i<=K+1;i++){
		run(i);
	}
	int pos = N;
	ll val = dp[K+1][pos].fs;
	vector<int> v;
	for(int i = K+1;i>1;i--){
		pos = dp[i][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:75:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   75 |  assert(v.size() == K);
      |         ~~~~~~~~~^~~~
sequence.cpp:85:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |  ^~~
sequence.cpp:85:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |  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: 0 / 29