Submission #737031

#	Time	Username	Problem	Language	Result	Execution time	Memory
737031		Abrar_Al_Samit	Split the sequence (APIO14_sequence)	C++17	100 / 100	1029 ms	84624 KiB

sequence

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

const int nax = 1e5 + 2;
const long long INF = 1e18;

int n, k;
long long a[nax], p[nax];
int par[nax][203];

struct line{
	long long m, c, id;
	line() {}
	line(long long _m, long long _c, long long _id) {
		m = _m, c = _c, id = _id;
	}

	long long eval(long long x) {
		return m * x + c;
	}
};
long long isecx(line a, line b) {
	return (long double) (b.c - a.c) / (long double) (a.m - b.m);
}
struct CHT{
	int sz = 0;

	deque<line>dq;
	void insert(line newLine) {
		while(sz>=2 && isecx(dq[sz-2], dq[sz-1])>=isecx(newLine, dq[sz-1])) {
			dq.pop_back();
			--sz;
		}
		dq.push_back(newLine);
		++sz;
	}
	pair<long long, long long> query(long long x) {
		while(sz>=2 && dq[0].eval(x)<=dq[1].eval(x)) {
			dq.pop_front();
			--sz;
		}
		return make_pair(dq[0].eval(x), dq[0].id);
	}
};
void PlayGround() {
	cin>>n>>k;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}

	for(int i=1; i<=n; ++i) {
		p[i] = p[i-1] + a[i];
	}


	vector<long long>dp(nax);
	for(int j=1; j<=k+1; ++j) {
		vector<long long>new_dp(nax);

		CHT myCHT;
		myCHT.insert(line(p[j-1], dp[j-1] - p[j-1] * p[n], j-1));

		for(int i=j; i<=n; ++i) {
			auto [y, id] = myCHT.query(p[i]);

			long long cons = p[i] * (p[n] - p[i]);
			new_dp[i] = cons + y;

			myCHT.insert(line(p[i], dp[i] - p[i] * p[n], i));

			par[i][j] = id;
		}

		// for(int i=j; i<=n; ++i) {
		// 	cerr<<new_dp[i]<<' ';
		// }
		// cerr<<'\n';
		dp.swap(new_dp);
	}

	cout<<dp[n]<<'\n';

	int cur = n, j = k+1;
	int cnt = k;
	while(1) {
		cur = par[cur][j];
		--j, --cnt;
		cout<<cur<<' ';
		if(cnt==0) break;
	}
	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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