Submission #976233

#	Time	Username	Problem	Language	Result	Execution time	Memory
976233		nnin	Split the sequence (APIO14_sequence)	C++14	100 / 100	760 ms	85344 KiB

sequence

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

int n, k;
int sum[100005];
int num[100005];

struct line {
    int m, c;
    int y(int x) {
        return m*x+c;
    }
};

int divv(int a, int b) {
    return a/b - ((a^b)<0 && a%b);
}
int isect(line a, line b) {
    if(a.m==b.m) return a.c<=b.c ? -1e18:1e18;
    return divv(a.c-b.c, b.m-a.m);
}

deque<pair<line, int>> cht;

int dp[100005][2];

pair<int,int> query(int x) {
    while(cht.size()>1 && cht[0].first.y(x)<=cht[1].first.y(x)) cht.pop_front();
    return {cht.front().first.y(x), cht.front().second};
}

void insert(line a, int i) {
    while(cht.size()>1 && isect(cht[cht.size()-2].first, cht.back().first)>=isect(cht[cht.size()-1].first, a)) cht.pop_back();
    cht.push_back({a, i});
}

int32_t idx[100005][205];

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>num[i];
        sum[i] = sum[i-1]+num[i];
    }
    int cur = 0;
    for(int i=0;i<k;i++) {
        cht.clear();
        insert({0, 0}, 0);
        for(int j=1;j<=n;j++) {
            auto p = query(sum[j]);
            dp[j][cur] = p.first;
            idx[j][i] = p.second;
            insert({sum[j], dp[j][1-cur]-(sum[j]*sum[j])}, j);
        }
        cur = 1-cur;
    }
    cout<<dp[n][1-cur]<<'\n';
    vector<int> ans;
    cur = n;
    for(int i=k-1;i>=0;i--) {
        ans.push_back(idx[cur][i]);
        cur = idx[cur][i];
    }
    for(int i=k-1;i>=0;i--) cout<<ans[i]<<' ';
}

/*
7 3
4 1 3 4 0 2 3
*/

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