Submission #624367

#	Time	Username	Problem	Language	Result	Execution time	Memory
624367		vovamr	Split the sequence (APIO14_sequence)	C++17	71 / 100	67 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct line {
	ll k, b; int id;
	line() : k(0), b(0), id(0) {}
	line(ll k, ll b, int id) : k(k), b(b), id(id) {}
	inline pll operator()(const ll &x) { return mpp(k * 1ll * x + b, id); }
};
inline bool bad(const line &a, const line &b, const line &c) {
	return (ld)(a.b - c.b) * (b.k - a.k) <= (ld)(c.k - a.k) * (a.b - b.b);
}
const int N = 3e5 + 100;
int sz; line s[N];
inline void add(line c) {
	if (!sz) return void(s[sz++] = c);
	if (s[sz - 1].k == c.k) {
		if (s[sz - 1].b <= c.b) return;
		else --sz;
	}
	while (sz >= 2) {
		const line &a = s[sz - 2];
		const line &b = s[sz - 1];
		if (bad(a, b, c)) --sz;
		else break;
	} s[sz++] = c;
}
int ptr = 0;
inline pll get(const ll x) {
	chmin(ptr, sz - 1);
	while (ptr + 1 < sz && s[ptr + 1](x) < s[ptr](x)) ++ptr;
	return s[ptr](x);
}

inline void solve() {
	int n, k;
	cin >> n >> k;
	ve<int> a(n);
	for (auto &i : a) cin >> i;

	ve<ll> s(n);
	for (int i = 0; i < n; ++i) {
		s[i] = a[i];
		if (i) s[i] += s[i - 1];
	}
	ve<ll> sq(n);
	for (int i = 0; i < n; ++i) {
		sq[i] = a[i] * a[i];
		if (i) sq[i] += sq[i - 1];
	}

	ve<ve<pll>> dp(k + 2, ve<pll>(n, mpp(inf, -1)));
	for (int i = 0; i < n; ++i) dp[1][i] = {s[i] * 1ll * s[i] - sq[i], -1};

	for (int z = 2; z <= k + 1; ++z) {
		sz = ptr = 0;
		for (int i = z - 2; i < n; ++i) {
			// dp[z][i] =    min  ((s[i] - s[j])^2 - (sq[i] - sq[j]) + dp[j])
			// 		j < i
			// = s[i]^2 - sq[i] + min(-2s[j] * s[i] + s[j]^2 + dp[j] + sq[j])
			if (sz) { pll c = get(s[i]); dp[z][i] = {c.fi + s[i] * s[i] - sq[i], c.se}; };
			if (dp[z - 1][i].fi != inf) add(line(-2 * s[i], s[i] * s[i] + dp[z - 1][i].fi + sq[i], i));
		}
//		cout << "layer " << z << ":" << '\n';
//		for (int i = 0; i < n; ++i) {
//			if (f[i] > 1e9) cout << -1 << " ";
//			else cout << f[i] << " ";
//		}
//		cout << '\n' << '\n';
//		dp.swap(f);
	}
	cout << (s[n - 1] * s[n - 1] - sq[n - 1] - dp[k + 1][n - 1].fi) / 2 << '\n';

	ve<int> ans;
	int x = k + 1, y = n - 1;

	while (x > 1) {
		ans.pb(dp[x][y].se + 1);
		tie(x, y) = mpp(x - 1, dp[x][y].se);
	}

	reverse(all(ans));
	for (auto i : ans) cout << i << " ";
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << 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: 0 / 29