Submission #1134355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134355		Math4Life2020	Split the sequence (APIO14_sequence)	C++17	100 / 100	802 ms	97444 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 1e5+5; const ll Km = 205; const ll INF = 1e18;
ll a[Nm];
ll psa[Nm+1];

//pii dp[Nm+1][Km+1]; //filled with zeroes initially: {value, previous index}
int dp[Nm+1][Km+1]; //just previous index now!

pii eval(array<ll,3> a1, ll x) {
	return {a1[0]*x+a1[1],a1[2]};
}

//vector<array<ll,3>> adp[Km+1];
deque<array<ll,3>> adp[Km+1];
//more positive to more negative slopes

pii rd(deque<array<ll,3>>& v1, ll x) {
	//read from front
	if (v1.size()==1) {
		return eval(v1.front(),x);
	}
	array<ll,3> t1 = v1.front(); v1.pop_front();
	array<ll,3> t2 = v1.front();
	pii p1 = eval(t1,x); pii p2 = eval(t2,x);
	if (p2.first<p1.first) {
		return rd(v1,x);
	} else {
		v1.push_front(t1); return p1;
	}
}

void anl(deque<array<ll,3>>& v1) {
	if (v1.size()<3) {
		return;
	}
	array<ll,3> t3 = v1.back(); v1.pop_back();
	array<ll,3> t2 = v1.back(); v1.pop_back();
	array<ll,3> t1 = v1.back();
	if (!((t3[1]*t1[0]+t1[1]*t2[0]+t2[1]*t3[0])>(t1[1]*t3[0]+t2[1]*t1[0]+t3[1]*t2[0]))) {
		v1.push_back(t3);
		anl(v1);
	} else {
		v1.push_back(t2);
		v1.push_back(t3);
	}
}

void wt(ll i, ll k, pii dpv) {
	adp[k].push_back({-2*psa[i],dpv.first+2*psa[i]*psa[i],i});
	anl(adp[k]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,K; cin >> N >> K;
	for (ll k=0;k<Km;k++) {
		adp[k].push_back({0,INF,-1});
	}
	psa[0]=0;
	for (ll i=0;i<N;i++) {
		cin >> a[i];
		psa[i+1]=psa[i]+a[i];
	}
	for (ll i=0;i<=N;i++) {
		if (i==0) {
			adp[0].push_back({0,0,0});
			continue;
		}
		for (ll k=Km;k>=1;k--) {
			//dp[i][k]=rd((adp[k-1]),psa[i]);
			pii pdp = rd((adp[k-1]),psa[i]);
			dp[i][k]=pdp.second;
			if (pdp.first==INF) {
				continue;
			}
			wt(i,k,pdp);
			if (i==N && k==(K+1)) {
				cout << (-pdp.first/2) <<"\n";
			}
		}
	}
	//cout << (-dp[N][K+1].first)/2 << "\n";
	string ansS;
	ll ip = N; ll kp = K+1;
	vector<ll> vip;
	while (kp>0) {
		vip.push_back(ip);
		ip = dp[ip][kp];
		kp--;
	}
	for (ll k=0;k<K;k++) {
		cout << vip[K-k];
		if (k != (K-1)) {
			cout << " ";
		}
	}
	cout << ansS << "\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