제출 #1203880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203880		Ghulam_Junaid	Split the sequence (APIO14_sequence)	C++20	100 / 100	1868 ms	89644 KiB

sequence

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

#define F first
#define S second
#define inf 1e12

typedef long long ll;
typedef pair<ll, ll> pii;

const ll N = 1e5 + 10, K = 205;
int n, k, a[N], par[N][K];
ll p[N];
vector<pair<ll, pii>> hull[K];

inline bool cmp(pii x, pii y){
    if ((x.F / x.S) != (y.F / y.S))
        return (x.F / x.S) > (y.F / y.S);
    x.F %= x.S;
    y.F %= y.S;
    return (x.F * y.S) > (y.F * x.S);
}

inline bool useful(pii x, pii y, pii z){
    return cmp({x.S - y.S, y.F - x.F}, {y.S - z.S, z.F - y.F});
}

inline void insert(int id, int ind, pii L){
    while (hull[id].size() and hull[id].back().S.F == L.F){
        if (hull[id].back().S.S < L.S)
            hull[id].pop_back();
        else
            return ;
    }
    while (hull[id].size() > 1 and !useful(hull[id][hull[id].size() - 2].S, hull[id].back().S, L))
        hull[id].pop_back();
    hull[id].push_back({ind, L});
}

inline ll f(pii L, ll x){
    return x * L.F + L.S;
}

inline pair<ll, int> query(int id, int ind, ll x){
    if (hull[id][0].F <= ind) return {-inf, -1}; 
    pair<ll, int> ans = {f(hull[id][0].S, x), hull[id][0].F};
    int lo = 0, hi = hull[id].size();
    
    while (hi - lo > 1){
        int mid = (lo + hi) / 2;
        if (hull[id][mid].F <= ind){
            hi = mid;
            continue;
        }

        ll ans1 = f(hull[id][mid - 1].S, x);
        ll ans2 = f(hull[id][mid].S, x);
        if (ans1 < ans2){
            ans = {ans2, hull[id][mid].F};
            lo = mid;
        }
        else{
            ans = {ans1, hull[id][mid - 1].F};
            hi = mid;
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for (ll i = 1; i <= n; i ++)
        cin >> a[i], p[i] = p[i - 1] + a[i];

    for (ll i = n; i > 0; i--)
        insert(k, i, {p[i - 1], 0 + p[n] * p[i - 1] -p[i - 1] * p[i - 1]});
    ll val;
    for (ll kk = k - 1; kk >= 0; kk --){
        for (ll i = n; i > 0; i --){
            auto P = query(kk + 1, i, p[i - 1]);
            val = P.F - p[n] * p[i - 1], par[i][kk] = P.S;
            insert(kk, i, {p[i - 1], val + p[n] * p[i - 1] -p[i - 1] * p[i - 1]});
        }
        hull[kk + 1].clear();
        hull[kk + 1].shrink_to_fit();
    }

    cout << val << '\n';
    int cur = 1;
    for (int kk = 1; kk <= k; kk ++){
        cur = par[cur][kk - 1];
        cout << cur - 1 << " ";
    }
    cout << '\n';
}

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