Submission #1202379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202379		adiyer	Split the sequence (APIO14_sequence)	C++20	50 / 100	2099 ms	179236 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 11;
const ll is_query = -(1ll << 62);

ll n, k;
ll a[N], p[N], sz[201];

pair < ll, ll > ans;
pair < ll, ll > dp[N][201];

struct Line {
    ll m, b, i;
    mutable function < const Line* () > succ;
    bool operator < (const Line& rhs) const {
    	if(rhs.b != is_query) return m < rhs.m;
    	const Line* s = succ();
    	return s ? b - s -> b < (s -> m - m) * rhs.m : 0;
    }
};

struct HullDynamic : public multiset<Line> {
	bool bad(iterator y) {
		auto z = next(y);
		if(y == begin()) {
			if(z == end()) return 0;
			return y -> m == z -> m && y -> b <= z -> b;
		}
		auto x = prev(y);
		if(z == end()) return y -> m == x -> m && y -> b <= x -> b;
		return (x -> b - y -> b) * (z -> m - y -> m) >= (y -> b - z -> b) * (y -> m - x -> m);
	}
	void insert_line(ll m, ll b, ll i) {
		auto y = insert({m, b, i});
		y -> succ = [=]{return next(y) == end() ? 0 : &*next(y);};
		if(bad(y)) {erase(y); return; }
		while(next(y) != end() && bad(next(y))) erase(next(y));
		while(y != begin() && bad(prev(y))) erase(prev(y));
	}
	pair < ll, ll > eval(ll x) {
		auto l = *lower_bound((Line) {x, is_query});
		return {l.m * x + l.b, l.i};
	}
} hull[201];


void solve(){
	cin >> n >> k;
	for(ll i = 0; i <= 200; i++) sz[i] = 1;
	for(ll i = 1; i <= n; i++) cin >> a[i], p[i] = p[i - 1] + a[i];
	hull[0].insert_line(0, 0, 0);
	for(ll i = 1; i < n; i++){
		for(ll lay = 1; lay <= min(i, k); lay++){
			dp[i][lay] = hull[lay - 1].eval(p[i] - p[n]);
			dp[i][lay].first += p[i] * (p[n] - p[i]);
			// cout << i << ' ' << lay << ' ' << dp[i][lay].second << ' ' << lay - 1 << ' ' << dp[i][lay].first << '\n';
		}
		for(ll lay = 1; lay <= min(i, k); lay++){
			hull[lay].insert_line(p[i], dp[i][lay].first, i);
			if(dp[i][lay].first >= ans.first) ans = {dp[i][lay].first, i};
		}
	}
	cout << ans.first << '\n';
	while(k > 0){
		cout << ans.second << ' ';
		ans = dp[ans.second][k];
		k--;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:39:29: warning: implicit capture of 'this' via '[=]' is deprecated in C++20 [-Wdeprecated]
   39 |                 y -> succ = [=]{return next(y) == end() ? 0 : &*next(y);};
      |                             ^
sequence.cpp:39:29: note: add explicit 'this' or '*this' capture

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