Submission #213280

#	Time	Username	Problem	Language	Result	Execution time	Memory
213280		someone_aa	Split the sequence (APIO14_sequence)	C++17	71 / 100	2101 ms	59768 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define pll pair<ll,ll>
using namespace std;
const ld inf = 1e18;
const ll infll = 1e18;
const int maxn = 100100;
ll arr[maxn], pref[maxn];
ll dp[210][maxn], n, k;
ll parent[210][maxn];

struct cht {
	struct line {
		ll k, b; ld x;
		ll val; bool isquery;
		ll ind;

		line (ll _k=0LL, ll _b=0LL, ll _ind=0) :
			k(_k), b(_b), x(-inf), val(0), isquery(false), ind(_ind) { }

		ll eval(ll x) const { return k*x+b; }
		bool parallel(const line &l) const { return k == l.k; }
		ld intersection(const line &l) const {
			if(parallel(l)) return inf;
			return (1.0*b - l.b) / (1.0*l.k - k);
		}

		bool operator <(const line &l) const {
			if(l.isquery) return  x < l.val;
			else return k < l.k;
		}
	};

	set<line>hull;
	typedef set<line>::iterator iter;

	bool cPrev(iter it) { return it != hull.begin(); }
	bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }

	bool bad(const line &l1, const line &l2, const line &l3) {
		return l1.intersection(l3) <= l1.intersection(l2);
	}
	bool bad(iter it) {
		return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
	}

	iter update(iter it) {
		if(!cPrev(it)) return it;

		line tmp(*it);
		ld x = tmp.intersection(*prev(it));
		tmp.x = x;

		it = hull.erase(it);
		return hull.insert(it, tmp);
	}
	void addline(ll k, ll b, ll ind) {
		line l(k, b, ind);
		iter it = hull.lower_bound(l);

		if(it != hull.end() && it->parallel(l)) {
			if(b > it->b) it = hull.erase(it);
			else return;
		}

		it = hull.insert(it, l);
		if(bad(it)) return (void) hull.erase(it);

		while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
		while(cNext(it) && bad(next(it))) hull.erase(next(it));

		it = update(it);
		if(cPrev(it)) update(prev(it));
		if(cNext(it)) update(next(it));
	}

	pll query(ll x) {
		if(hull.empty()) return mp(-infll, -1LL);

		line tmp;
		tmp.val = x; tmp.isquery = true;
		iter it = --hull.lower_bound(tmp);

		return mp(it->eval(x), it->ind);
	}
};

int main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
		pref[i] = pref[i-1] + arr[i];
	}

	for(int d=1;d<=k;d++) {
		if(d == 1) {
			for(int i=1;i<n;i++) {
				dp[d][i] = pref[i] * (pref[n] - pref[i]);
			}
			continue;
		}

		cht ds;
		for(int i=d;i<n;i++) {
			// add info for state(d-1, i-1)
			ds.addline(pref[i-1], dp[d-1][i-1] - pref[i-1]*pref[n], i-1);
			pll curr = ds.query(pref[i]);
			dp[d][i] = curr.first + pref[i]*pref[n] - pref[i] * pref[i]; 
			parent[d][i] = curr.second;
		}
	}

	ll result = -inf;
	ll resultind = -1;
	for(int i=k;i<n;i++) {
		if(dp[k][i] > result) {
			result = dp[k][i];
			resultind = i;
		}
	}
	cout<<result<<"\n";
	vector<int>v;
	for(int i=k;i>=1;i--) {
		v.pb(resultind);
		resultind = parent[i][resultind];
	}
	reverse(v.begin(), v.end());
	for(int i:v) {
		cout<<i<<" ";
	} cout<<"\n";
}

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