Submission #1254883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254883		nanaseyuzuki	Split the sequence (APIO14_sequence)	C++20	0 / 100	72 ms	158784 KiB

sequence

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <-- (modified: added trace output)
    I love Nanasaki Ai ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
using namespace std;

const int mn = 1e5 + 1;
const int inf = 1e18;

int n, k, a[mn], dp[201][mn], prefix[mn], par[201][mn];

// dp[i][j] = max(dp[i - 1][j1] + (prefix[j] - prefix[j1]) * (prefix[n] - prefix[j]))

struct line{
    double x, y;
    int fi;
};

double center(line a, line b){
    return (a.y - b.y) / (b.x - a.x);
}

deque <line> reina;
deque <pair<double, int>> pts;

void add(line kumiko){
    while(reina.size() >= 1 && kumiko.x == reina.front().x && kumiko.y >= reina.front().y){
        reina.pop_front();
        pts.pop_front();
    }
    while(reina.size() >= 2 && center(kumiko, reina.front()) >= pts.front().fi){
        reina.pop_front();
        pts.pop_front();
    }
    if(pts.size()) pts.push_front({center(reina.front(), kumiko), kumiko.fi});
    else pts.push_front({1e9, kumiko.fi});
    reina.push_front(kumiko);
}


pii query(int x){
    if(pts.empty()) return {-inf, 0};
    int id = upper_bound(pts.begin(), pts.end(), pair<double,int>((double)x, 0),
        [](const pair<double,int>& val, const pair<double,int>& elem){
            return val.first < elem.first;
        }
    ) - pts.begin();
    return {(int)reina[id].x * x + reina[id].y, pts[id].se}; 
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    fill(&dp[0][0], &dp[0][0] + mn * 205, -inf);
    dp[0][0] = 0;
    for(int i = 1; i <= k + 1; i++){
        reina.clear();
        pts.clear();
        if(dp[i - 1][i - 1] != -inf){
            line y = { (double)prefix[i - 1], (double)- dp[i - 1][i - 1], i - 1};
            add(y);
        }
        for(int j = i; j <= n - (k + 1 - i); j++){
            int val = prefix[n] - prefix[j];
            pii best = query(val);
            dp[i][j] = - best.fi + prefix[j] * (prefix[n] - prefix[j]);
            par[i][j] = best.se;
            if(dp[i - 1][j] != -inf){
                line x = { (double)prefix[j], (double)- dp[i - 1][j], j};
                add(x);
            }
        }
    }
    cout << dp[k + 1][n] << '\n';
    if(dp[k + 1][n] == -inf){
        return;
    }
    vector<int> cuts;
    int ci = k + 1;
    int cj = n;
    while(ci > 0){
        cuts.push_back(cj);
        int prev = par[ci][cj];
        cj = prev;
        ci--;
    }
    reverse(cuts.begin(), cuts.end());
    vector<int> out;
    for(int x : cuts) if(x > 0) out.push_back(x);
    if(out.size() > 1){
        for(int idx = 0; idx < (int)out.size() - 1; idx++){
            if(idx) cout << ' ';
            cout << out[idx];
        }
        cout << '\n';
    }
    else{
        cout << '\n';
    }

}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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