Submission #197021

#	Time	Username	Problem	Language	Result	Execution time	Memory
197021		Juney	Split the sequence (APIO14_sequence)	C++14	100 / 100	462 ms	85512 KiB

sequence

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5 + 5;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

ll N, K, A[MAXN], dp[2][MAXN], S[MAXN];
int path[205][MAXN];

struct func {
	ll a, b, idx;
	double s;
	func(ll x, ll y, int z) : a(x), b(y), idx(z) { s = -INF; };
	func() {}
	ll val(ll x) { return a*x + b; }
};

double cross(func &f, func &g) { return (double)(g.b - f.b) / (double)(f.a - g.a); }

func st[MAXN];
void solve(int k) {
	int idx = 0, sz = 0;
	for(int i=k+1; i<=N; i++) {
		func f(S[i-1], dp[(k+1) % 2][i-1] - S[i-1]*S[i-1], i-1);
		bool flag = 0;
		while(sz) {
			if(f.a == st[sz-1].a) {
				if(st[sz-1].b < f.b) sz--, idx = min(idx, sz-1);
				else {
					flag = 1;
					break;
				}
			}
			if(sz == 0) break;
			f.s = cross(f, st[sz-1]);
			if(f.s > st[sz-1].s) break;
			sz--; idx = min(idx, sz-1);
		}
		if(!flag) st[sz++] = f;
		while(idx+1 < sz && st[idx+1].s <= S[i]) idx++;
		dp[k%2][i] = st[idx].val(S[i]);
		path[k][i] = st[idx].idx;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	for(int i=1; i<=N; i++) cin >> A[i], S[i] = S[i-1] + A[i];
	for(int k=1; k<=K; k++) solve(k);
	cout << dp[K%2][N] << '\n';
	vector<int> ans;
	int x = N;
	for(int k=K; k>=1; k--) ans.push_back(path[k][x]), x = path[k][x];
	reverse(ans.begin(), ans.end());
	for(auto i : ans) cout << i << ' ';
}

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