Submission #1303839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303839		nathlol2	Split the sequence (APIO14_sequence)	C++20	100 / 100	638 ms	82700 KiB

sequence

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 111111;
int n, k, pf[N];
int32_t r[N][201];
vector<int> ans;
struct line{
    int m, c, id;
    int v(int x){
        return m*x + c;
    }
};
struct container{
    deque<line> dq;
    void add(line nw){
        while(dq.size() >= 2){
            line A = dq[dq.size() - 2];
            line B = dq.back();
            if((A.c - nw.c) * (B.m - A.m) >= (A.c - B.c) * (nw.m - A.m)){
                dq.pop_back();
            }else{
                break;
            }
        }
        dq.push_back(nw);
    }
    pair<int, int> qry(int x){
        while(dq.size() >= 2){
            if(dq[0].v(x) <= dq[1].v(x)){
                dq.pop_front();
            }else{
                break;
            }
        }
        return {dq[0].v(x), dq[0].id};
    }
    void clear(){
        while(dq.size()) dq.pop_back();
    }
}c;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i = 1;i<=n;i++){
        cin >> pf[i];
        pf[i] += pf[i - 1];
    }
    vector<int> dp(n + 1), prev(n + 1);
    for(int s = 1;s<=k;s++){
        c.clear();
        c.add({0, prev[0], 0});
        for(int i = 1;i<=n;i++){
            auto [x, id] = c.qry(pf[n] - pf[i]);
            dp[i] = pf[i] * (pf[n] - pf[i]) + x;
            r[i][s] = id;
            c.add({-pf[i], prev[i], i});
        }
        prev.swap(dp);
    }
    int mx = -1, id;
    for(int i = 1;i<=n;i++){
        if(prev[i] > mx){
            mx = prev[i];
            id = i;
        }
    }
    for(int i = k;i>0;i--){
        ans.push_back(id);
        id = r[id][i];
    }
    reverse(ans.begin(), ans.end());
    cout << mx << '\n';
    for(auto x : ans) cout << x << ' ';
}

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