Submission #1202278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202278		adiyer	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	320 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, ans;
ll a[N], p[N], dp[N][201], sz[201];

struct Line {
    ll m, b;
    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) {
		auto y = insert({m, b});
		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));
	}
	ll eval(ll x) {
		auto l = *lower_bound((Line) {x, is_query});
		return l.m * x + l.b;
	}
} 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);
	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]) + p[i] * (p[n] - p[i]);
			hull[lay].insert_line(p[i], dp[i][lay]);
			ans = max(ans, dp[i][lay]);
		}
	}
	cout << ans;
}

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

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