Submission #1200207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200207		Ghulam_Junaid	Split the sequence (APIO14_sequence)	C++20	71 / 100	217 ms	64268 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 = 1e4 + 100, K = 205;
ll n, k, a[N];
ll p[N], dp[N][K];
vector<pair<ll, pii>> hull[K];

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);
}

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});
}

void insert(ll id, ll 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});
}

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

ll query(ll id, ll ind, ll x){
    if (hull[id][0].F <= ind) return -inf; 
    ll ans = f(hull[id][0].S, x);
    ll lo = 0, hi = hull[id].size();
    
    while (hi - lo > 1){
        ll 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;
            lo = mid;
        }
        else{
            ans = ans1;
            hi = mid;
        }
    }
    return ans;
}

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

    for (ll i = 0; i < N; i ++)
        for (ll j = 0; j < k; j ++)
            dp[i][j] = -inf;

    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]});
    for (ll kk = k - 1; kk >= 0; kk --){
        for (ll i = n; i > 0; i --){
            dp[i][kk] = query(kk + 1, i, p[i - 1]) - p[n] * p[i - 1];
            insert(kk, i, {p[i - 1], dp[i][kk] + p[n] * p[i - 1] -p[i - 1] * p[i - 1]});
        }
    }

    cout << dp[1][0] << endl;
    int cur = 1;
    for (int kk = 1; kk <= k; kk ++){
        for (int j = cur + 1; j <= n; j ++){
            if (dp[cur][kk - 1] == dp[j][kk] + (p[j - 1] - p[cur - 1]) * (p[n] - p[j - 1])){
                cur = j;
                break;
            }
        }
        cout << cur - 1 << " ";
    }
    cout << endl;
}

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