Submission #797532

#	Time	Username	Problem	Language	Result	Execution time	Memory
797532		beaboss	Split the sequence (APIO14_sequence)	C++14	0 / 100	13 ms	10068 KiB

sequence

// Source: https://docs.google.com/document/d/1ryBjActxSlAAeTMRNUmJzWOGQ21ZuS32mQYTD8rHXzE/edit

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)


struct line {
	ll m, b;
	ll eval(ll x) {return m * x + b; }
	ll isectX(line l) {return (l.b - b) / (m - l.m); }
};

vector<deque<line> > lines(300);

vi ints(1000000);

void add(ll i, line l) {

	while (lines[i].size() > 1 && ((l.m == lines[i].back().m) || l.isectX((lines[i].back())) <= l.isectX((lines[i][lines[i].size() - 1])))) {
		lines[i].pop_back();
	}
	lines[i].push_back(l);
}


ll query(ll i, ll x) {
	// if (lines[i].size() > 1) cout << lines[i][1].m << ' ' << lines[i][1].b << endl;
	while (lines[i].size() > 1 && lines[i][0].isectX(lines[i][1]) < x) {

		lines[i].pop_front();
	}

	return lines[i][0].eval(x);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	iota(ints.begin(), ints.end(), 0);

	ll n, k;
	cin >> n >> k;

	vi vals(n + 1);
	vi pref(n + 1);

	FOR(i, 1, n + 1) {
		cin >> vals[i];
		pref[i] = vals[i] + pref[i-1];
	}

	add(0, {0, 0});

	ll ans = 0;

	FOR(i, 1, n + 1) {
		for (ll j = k; j>= 1; j--) {
			ll cur = pref[i] * pref[n] - pref[i] * pref[i] + query(j-1, pref[i]);
			// cout << i << j << cur << endl;
			add(j, {pref[i], cur - pref[i] * pref[n]});

			if (j == k) ans = max(ans, cur);
		}
	}

	cout << ans << endl;
}

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