Submission #397637

#	Time	Username	Problem	Language	Result	Execution time	Memory
397637		ocarima	Split the sequence (APIO14_sequence)	C++14	0 / 100	64 ms	86820 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

// APIO 2014 - Split the sequence (Convex Hull Trick)

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

#define MAX_N 100003
#define MAX_K 201

lli n, k, K, a[MAX_N], m[MAX_N], ord[MAX_N], dp[2][MAX_N];
lli act, pre;
long double sigcruce[MAX_N], prevcruce[MAX_N];
int corteprevio[MAX_N][MAX_K];
vlli cortes;
deque<lli> cht;

#define eval(r, x) (m[r] * x + ord[r])
#define inter(r1, r2) ((ord[r2] - ord[r1] + 0.0) / (m[r1] - m[r2] + 0.0))
#define INF (1e18)

int main()
{
    fastio;

    cin >> n >> K;
    rep(i, 1, n) cin >> a[i];
    rep(i, 2, n) a[i] += a[i - 1];

    pre = 0;
    act = 1;
    rep(k, 1, K){
        // VACIA LA COLA
        while(!cht.empty()) cht.pop_back();

        // INSERTA LA PRIMERA RECTA
        prevcruce[k] = 0;
        sigcruce[k] = INF;
        m[k] = a[k];
        ord[k] = dp[pre][k] -(a[k] * a[k]);
        cht.push_back(k);

        rep(i, k + 1, n){

            // ELIMINA DEL CHT LOS PUNTOS PREVIOS
            while (!cht.empty() && sigcruce[cht.front()] < a[i]) cht.pop_front();
            dp[act][i] = eval(cht.front(), a[i]);
            corteprevio[i][k] = cht.front();

            // CREA LA NUEVA RECTA
            m[i] = a[i];
            ord[i] = dp[pre][i] - (a[i] * a[i]);
            while(!cht.empty() && prevcruce[cht.back()] > inter(cht.back(), i)) cht.pop_back();

            if (cht.empty()) prevcruce[i] = 0;
            else prevcruce[i] = sigcruce[cht.back()] = inter(cht.back(), i);

            sigcruce[i] = INF;
            cht.push_back(i);
        }

        swap(pre, act);
    }

    cout << dp[pre][n] << nl;

    act = n;
    repa(k, K, 1){
        cortes.pb(corteprevio[act][k]);
        act = corteprevio[act][k];
    }
    reverse(cortes.begin(), cortes.end());
    repv(corte, cortes) cout << corte << " ";


    return 0;
}

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