Submission #800979

#	Time	Username	Problem	Language	Result	Execution time	Memory
800979		beaboss	Split the sequence (APIO14_sequence)	C++14	0 / 100	83 ms	52960 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<ll > > indexes(300);
 
vi lls(1000000);
 
void add(ll i, line l, ll ind) {
 
	while (lines[i].size() > 1 && ((l.m == lines[i].back().m) || l.isectX((lines[i].back())) <= l.isectX((lines[i][lines[i].size() - 2])))) {
		lines[i].pop_back();
		indexes[i].pop_back();
	}

	lines[i].push_back(l);
	indexes[i].push_back(ind);

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

		lines[i].pop_front();
		indexes[i].pop_front();
	}

	// cout << indexes[i][0] << endl;
 
	return {lines[i][0].eval(x), indexes[i][0]};
}
 
ll prv[10005][201];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	iota(lls.begin(), lls.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;
	ll 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;
			// if (lines[1].size() > 1) cout << lines[1][0].isectX(lines[1][1]) << endl;
 			// cout << i << j << ' ' << cur << endl;
			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;
 
	ll cur_n = best;
	
	for (ll 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:105:9: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |   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