제출 #138005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138005		Runtime_error_	Split the sequence (APIO14_sequence)	C++14	39 / 100	39 ms	3576 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e3+9,K=209,MX=1e9+9;
ll n,k,ans=-MX,idx;
ll pre[inf],a[inf];
pair<ll,ll> dp[K][inf];
vector<ll> split;

bool Q ;
struct Line {
	mutable ll m, p, k,idx;
	bool operator<(const Line& o) const {
		return Q ? k < o.k : m < o.m;
	}
};

struct LineContainer : multiset<Line> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
    }

	bool isect(iterator x, iterator y) {
		if (y == end()) {
		     x->k = inf;
		     return false;
        }
		if (x->m == y->m)
            x->k = x->p > y->p ? inf : -inf;
		else
            x->k = div(y->p - x->p, x->m - y->m);
		return x->k >= y->k;
	}
	void add(ll m, ll p,ll idx) {
		auto z = insert({m, p, 0,idx}), y = z++, x = y;
		while (isect(y, z))
            z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->k >= y->k)
			isect(x, erase(y));
	}
	pair<ll,ll> query(ll x) {
	        if(empty())
	            return {-MX,0};

		assert(!empty());
		Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
		return make_pair(l.m * x + l.p,l.idx);
	}
};


int main(){

    cin>>n>>k;
    for(ll i=1;i<=n;i++)
        cin>>a[i],pre[i]=pre[i-1]+a[i];

    for(ll j=1;j<=k;j++){
        LineContainer lc;
        lc.add(0,0,0);
        for(ll i=1;i<=n;i++){
            dp[j][i] = lc.query(pre[i]);
            dp[j][i].first += pre[i]*pre[n] - pre[i]*pre[i] ;
            lc.add(pre[i],dp[j-1][i].first-pre[i]*pre[n],i);

        }
    }

    for(ll i=1;i<=n;i++)
        if(ans<dp[k][i].first)
            ans=dp[k][i].first,idx=i;

    split.push_back(idx);
    for(ll j=k;j>1;j--)
        idx=dp[j][idx].second,split.push_back(idx);

    reverse(split.begin(),split.end());

    cout<<ans<<endl;
    for(auto o:split)
        cout<<o<<" ";
    cout<<endl;
}

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