Submission #1226415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226415		nrg_studio	Split the sequence (APIO14_sequence)	C++20	100 / 100	549 ms	83112 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 1e5+1, MAX_K = 201;
int a[MAX_N];
ll ss[MAX_N], ps[MAX_N];
int dp_prev[MAX_K][MAX_N];
vec<ll> dp(MAX_N), dp2(MAX_N);

double isect(pair<ll,ll> a, pair<ll,ll> b) {return (double)(a.s-b.s)/(b.f-a.f);}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, k; cin >> n >> k;

    for (int i=0;i<n;i++) {cin >> a[i+1];}
    ss[n+1] = ps[0] = 0;
    for (int i=n;i;i--) {ss[i] = ss[i+1]+a[i];}
    for (int i=1;i<=n;i++) {ps[i] = ps[i-1]+a[i];}

    fill(dp.begin(),dp.end(),0);
    deque<pair<pair<ll,ll>,int>> q;

    for (int i=1;i<=k;i++) {
        q.push_back({{-ps[i-1],dp[i-1]},i-1});

        for (int j=i;j<=n-1;j++) {
            while (q.size()>1 && isect(q.back().f,q.end()[-2].f)>=ss[j+1]) {q.pop_back();}
            dp2[j] = q.back().f.f*ss[j+1]+q.back().f.s+ps[j]*ss[j+1];
            dp_prev[i][j] = q.back().s;
            pair<pair<ll,ll>,int> line = {{-ps[j],dp[j]},j};
            while ((q.size() && q.front().f==line.f && q.front().s<=line.s) || (q.size()>1 && isect(line.f,q[1].f)>=isect(q[0].f,q[1].f))) {q.pop_front();}
            if (i!=1) {q.push_front(line);}
        }
        swap(dp,dp2); q.clear();
    }
    pair<ll,int> last = {0,0};
    for (int i=k;i<=n-1;i++) {chmax(last,make_pair(dp[i],i));}
    stack<int> ans;
    for (int i=k;i;i--) {
        ans.push(last.s);
        last.s = dp_prev[i][last.s];
    }
    cout << last.f << '\n';
    while (ans.size()) {
        cout << ans.top() << ' '; ans.pop();
    }

    /*
    (a+b)(c+d)
    ac+ad + bc+bd
    +ab+cd

    a(b+c+d)
    ab+ac+ad+bc+bd+cd
    
    max(dp[j]+(ps[i]-ps[j])ss[i+1])
    -ps[j]ss[i+1]+dp[j]+ps[i]ss[i+1]
    decreasing queries, decreasing slopes, max hull

    */
}

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