Submission #1303832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303832		nathlol2	Split the sequence (APIO14_sequence)	C++20	22 / 100	2 ms	1136 KiB

sequence

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 111111;
int n, k, pf[N], dp[N][202], r[N][202];
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};
    }
}c[202];
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];
    }
    c[0].add({-pf[0], 0, 0});
    for(int i = 1;i<=n;i++){
        for(int s = 1;s<=k;s++){
            auto [x, id] = c[s - 1].qry(pf[n] - pf[i]);
            dp[i][s] = pf[i] * (pf[n] - pf[i]) + x;
            c[s].add({-pf[i], dp[i][s], i});
            r[i][s] = id;
        }
        c[0].add({-pf[i], 0, i});
        for(int s = 1;s<=k + 1;s++){
            c[s].add({-pf[i], dp[i][s], i});
        }
    }
    int mx = -1, id;
    for(int i = 1;i<=n;i++){
        if(dp[i][k] > mx){
            mx = dp[i][k];
            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: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29