Submission #1271836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271836		crispxx	Split the sequence (APIO14_sequence)	C++20	71 / 100	2098 ms	171632 KiB

sequence

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

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

const int inf = 1e18;

struct line {
	int m, b, idx;
	line() : m(0), b(-inf), idx(-1) {}
	line(int m, int b, int idx) : m(m), b(b), idx(idx) {}
};

int operator * (const line &l, int x) {
	return l.m * x + l.b;
}

struct LiChao {
	int n;
	vector<int> q;
	vector<line> t;
	
	LiChao(vector<int> a) : n(a.size()), q(a), t(n << 2) {
		sort(all(q));
	}
	
	void add(int v, int l, int r, line u) {
		int m = (l + r) >> 1;
		
		if(t[v] * q[m] < u * q[m]) {
			swap(t[v], u);
		}
		
		if(l == r) return;
		
		if(t[v] * q[l] < u * q[l]) {
			add(v << 1, l, m, u);
		} else {
			add(v << 1 | 1, m + 1, r, u);
		}
	}
	
	void add(int m, int b, int i) {
		add(1, 0, n - 1, line(m, b, i));
	}
	
	int get(int v, int l, int r, int i) {
		if(l == r) return v;
		int m = (l + r) >> 1;
		int opt;
		if(i <= m) {
			opt = get(v << 1, l, m, i);
		} else {
			opt = get(v << 1 | 1, m + 1, r, i);
		}
		if(t[v] * q[i] > t[opt] * q[i]) opt = v;
		return opt;
	}
	
	int get(int x) {
		int i = lower_bound(all(q), x) - q.begin();
		return t[get(1, 0, n - 1, i)].idx;
	}
};

void solve() {
	int n, k; cin >> n >> k;
	
	vector<int> a(n);
	
	for(auto &x : a) cin >> x;
	
	vector<int> pref(n + 1);
	
	for(int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
	
	vector<int> dp(n + 1);
	vector<vector<int>> p(k + 1, vector<int>(n + 1));
	
	for(int i = 0; i <= k; i++) {
		LiChao t(pref);
		vector<int> ndp(n + 1, -inf);
		
		for(int j = 0; j <= n; j++) {
			int l = t.get(pref[j]);
			if(l != -1) {
				ndp[j] = dp[l] + (pref[j] - pref[l]) * (pref[n] - pref[j]);
				p[i][j] = l;
			}
			t.add(pref[j], dp[j] - pref[j] * pref[n], j);
		}
		
		swap(dp, ndp);
	}
	
	cout << dp[n] << nl;
	
	for(int i = k, j = n; i >= 1; i--) {
		j = p[i][j];
		cout << j << ' ';
	}
	
	cout << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

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