Submission #558640

#	Time	Username	Problem	Language	Result	Execution time	Memory
558640		fuad27	Split the sequence (APIO14_sequence)	C++17	60 / 100	517 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e18;

ll pre[100'010][210];
struct LiChao_max {
	struct line {
		ll a, b;
		ll in;
		line(){a=0,b=0;}
		line(ll _a, ll _b, ll _in){a=_a,b=_b,in=_in;}
		ll val(ll x){return a*x+b;}
	};
	struct node {
		line f;
		node* l, *r;
		node(){f=line(),l=nullptr,r=nullptr;}
		node(line v){f=v,l=nullptr,r=nullptr;}
		node(ll a, ll b, ll in){f=line(a, b, in),l=nullptr,r=nullptr;}
	};
	ll sz;
	node* root;
	void init(ll _sz){sz=_sz+1,root=nullptr;}
	void add_line(ll a, ll b, ll in){line v = line(a, b, in);insert(v, -sz, sz, root);}
	line query(ll x){return query(x, -sz, sz, root);}
	void insert(line v, ll l, ll r, node*& nd) {
		if(nd == nullptr){nd=new node(v);return;}
		ll tl = nd->f.val(l), tr = nd->f.val(r);
		ll vl = v.val(l), vr = v.val(r);
		if(tl >= vl and tr >= vr)return;
		if(tl < vl and tr < vr){std::swap(nd->f, v);return;}
		if(tl < vl)std::swap(nd->f, v);
		ll mid = (l+r)/2;
		if(nd->f.val(mid) < v.val(mid)) {
			std::swap(nd->f, v);
			insert(v, l, mid, nd->l);
		}
		else {
			insert(v, mid+1, r, nd->r);
		}
	}
	line query(ll x, ll l, ll r, node*& nd) {
		if(nd == nullptr)return line(0, 0, -1);
		if(l == r)return nd->f;
		ll mid = (l+r)/2;
		if(x <= mid) {
			line v = query(x, l, mid, nd->l);
			if(v.val(x) > nd->f.val(x))return v;
			return nd->f;
		}
		else {
			line v = query(x, mid+1, r, nd->r);
			if(v.val(x) > nd->f.val(x))return v;
			return nd->f;
		}
	}
};
int main () {
	LiChao_max l;
	int n, k;
	cin >> n >> k;
	long long arr[n];
	for(int i = 0;i<n;i++) {
		cin >> arr[i];
	}
		if(n == 2) {
		long long ans = arr[0] * arr[1];
		cout << ans << "\n";
		cout << 1 << "\n";
		return 0;
	}
	long long pref[n+1];
	pref[0] = 0;
	for(int i = 1;i<=n;i++)pref[i] = pref[i-1] + arr[i-1];
	vector<long long> dp[2];
	for(int i = 0;i<2;i++)dp[i].resize(n+1);
	for(int j = 0;j<k;j++) {
		l.init(1e9 + 1);
		for(int i = 1;i<=n;i++) {
			pre[i-1][j] = -1;
			LiChao_max::line v = l.query(pref[n]-pref[i]);
			dp[1][i] = v.val(pref[n]-pref[i]) + pref[i]*(pref[n]-pref[i]);
			l.add_line(-pref[i], dp[0][i], i-1);
			pre[i-1][j]=v.in;
			if(j == 0)pre[i-1][j] = -1;
			// cout << dp[1][i] << " ";
		}
		dp[0].swap(dp[1]);
	}
	ll mx = -1, idx = -1;
	for(int i = 0;i<n;i++) {
		if(dp[0][i+1] >= mx) {
			mx = dp[0][i+1];
			idx = i;
		}
	}
	cout << mx << "\n";
	k--;
	while(idx!=-1 and k >= 0) {
		cout << idx+1 << " ";
		idx = pre[idx][k];
		k--;
	}
	cout << "\n";
}

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