Submission #942073

#	Time	Username	Problem	Language	Result	Execution time	Memory
942073		yellowtoad	Split the sequence (APIO14_sequence)	C++17	100 / 100	796 ms	113420 KiB

sequence

#include <iostream>
#include <queue>
#include <vector>
#define f first
#define s second
using namespace std;

long long n, k, ps[100010], dp[210], cur;
int p[100010][210];
deque<pair<pair<long double,pair<long long,long long>>,int>> dq[210];

long double pt(long double m1, long double c1, long double m2, long double c2) {
	return (c2-c1)/(m1-m2);
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> ps[i];
		ps[i] += ps[i-1];
	}
	for (int i = 1; i < n; i++) {
		for (int j = k; j >= 1; j--) {
			if (j == 1) {
				if ((j == k) && (dp[j] <= ps[i]*(ps[n]-ps[i]))) cur = i;
				dp[j] = max(dp[j],ps[i]*(ps[n]-ps[i]));
			} else {
				while ((dq[j-1].size()) && (dq[j-1].front().f.f < ps[i])) dq[j-1].pop_front();
				if (dq[j-1].size()) {
					if (dp[j] < dq[j-1].front().f.s.f*ps[i]+dq[j-1].front().f.s.s+ps[n]*ps[i]-ps[i]*ps[i]) {
						if (j == k) cur = i;
						p[i][j] = dq[j-1].front().s;
					} else p[i][j] = p[i-1][j];
					dp[j] = max(dp[j],dq[j-1].front().f.s.f*ps[i]+dq[j-1].front().f.s.s+ps[n]*ps[i]-ps[i]*ps[i]);
				}
			}
			if ((dq[j].size()) && (ps[i] == dq[j].back().f.s.f)) {
				if (dq[j].back().f.s.f > dp[j]-ps[n]*ps[i]) goto skip;
				else dq[j].pop_back();
			}
			while ((dq[j].size() >= 2) && (dq[j][dq[j].size()-2].f.f > pt(dq[j][dq[j].size()-2].f.s.f,dq[j][dq[j].size()-2].f.s.s,ps[i],dp[j]-ps[n]*ps[i]))) dq[j].pop_back();
			if (dq[j].size()) dq[j].back().f.f = pt(dq[j].back().f.s.f,dq[j].back().f.s.s,ps[i],dp[j]-ps[n]*ps[i]);
			if (dp[j] != 0) dq[j].push_back({{1e18,{ps[i],dp[j]-ps[n]*ps[i]}},i});
			skip:;
		}
	}
	cout << dp[k] << endl;
	for (int i = k; i >= 1; i--) {
		cout << cur << " ";
		cur = p[cur][i];
	}
	cout << endl;
}

/*
7 3
4 1 3 4 0 2 3
*/

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