oj.uz

Submission #397640

# Submission time Handle Problem Language Result Execution time Memory
397640 2021-05-02T16:32:53 Z ocarima Split the sequence (APIO14_sequence) C++14
0 / 100
 58 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[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]);
            if (m[i] || ord[i] && m[i] > m[i - 1]){
                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;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:67:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   67 |             if (m[i] || ord[i] && m[i] > m[i - 1]){
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~

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 Correct 1 ms 332 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 332 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 1 ms 332 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 1 ms 332 KB contestant found the optimal answer: 1 == 1
7 Correct 1 ms 332 KB contestant found the optimal answer: 1 == 1
8 Correct 1 ms 332 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 332 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 1 ms 332 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 1 ms 332 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 332 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Incorrect 1 ms 332 KB contestant didn't find the optimal answer: 140067 < 140072
14 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 contestant didn't find the optimal answer: 484133 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8908 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 58 ms 86792 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -