oj.uz

Submission #397631

# Submission time Handle Problem Language Result Execution time Memory
397631 2021-05-02T15:58:24 Z ocarima Split the sequence (APIO14_sequence) C++14
0 / 100
 61 ms 86792 KB 
#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[0] = 0;
        sigcruce[0] = INF;
        cht.push_back(0);

        rep(i, 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 332 KB contestant found the optimal answer: 999 == 999
3 Incorrect 1 ms 332 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Integer 0 violates the range [1, 199]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1228 KB Integer 0 violates the range [1, 999]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9036 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 86792 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -