Submission #1254891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254891		nanaseyuzuki	Split the sequence (APIO14_sequence)	C++20	100 / 100	1435 ms	85940 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<ll, int>
#define ll long long int
using namespace std;

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

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

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

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

double center(line a, line b){
    return (double)(a.y - b.y) / (double)(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(ll 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 {(ll)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 * 2, -inf);
    dp[0][0] = 0;
    for(int i = 1; i <= k + 1; i++){
        int cur = i % 2, pre = 1 - cur;
        for(int j = 0; j < mn; j++) dp[cur][j] = -inf;
        reina.clear();
        pts.clear();
        if(dp[pre][i - 1] != -inf){
            line y = { prefix[i - 1], -dp[pre][i - 1], i - 1};
            add(y);
        }
        for(int j = i; j <= n - (k + 1 - i); j++){
            ll val = prefix[n] - prefix[j];
            pii best = query(val);
            dp[cur][j] = - best.fi + prefix[j] * (prefix[n] - prefix[j]);
            par[i][j] = best.se;
            if(dp[pre][j] != -inf){
                line x = {prefix[j], -dp[pre][j], j};
                add(x);
            }
        }
    }
    cout << dp[(k + 1) % 2][n] << '\n';
    if(dp[(k + 1) % 2][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();
    }
}

Compilation message (stderr)

sequence.cpp:13:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   13 | const int inf = 1e18;
      |                 ^~~~

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