Submission #797534

#	Time	Username	Problem	Language	Result	Execution time	Memory
797534		beaboss	Split the sequence (APIO14_sequence)	C++14	0 / 100	26 ms	36384 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);
vector<deque<int > > indexes(300);

vi ints(1000000);

void add(ll i, line l, int ind) {

	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();
		indexes[i].pop_back();
	}
	lines[i].push_back(l);
	indexes[i].push_back(ind);
}


pii 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();
		indexes[i].pop_front();
	}

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

int prv[10005][201];
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}, 0);


	ll ans = 0;
	int best;
	FOR(i, 1, n + 1) {
		for (ll j = k; j>= 1; j--) {
			pii q = query(j-1, pref[i]);
			ll cur = pref[i] * pref[n] - pref[i] * pref[i] + q.f;
			prv[i][j] = q.s;

			add(j, {pref[i], cur - pref[i] * pref[n]}, i);

			if (j == k) {
				if (cur > ans) best = i;
				ans = max(ans, cur);
			}
		}
	}

	cout << ans << endl;

	int cur_n = best;
	
	for (int cur_k = k; cur_k > 0; cur_k--) {
		cout << cur_n << ' ';
		cur_n = prv[cur_n][cur_k];
	}

	cout << endl;

	
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:98:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |   cur_n = prv[cur_n][cur_k];
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~

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