oj.uz

Submission #885473

# Submission time Handle Problem Language Result Execution time Memory
885473 2023-12-09T19:53:28 Z charleehp Boxes with souvenirs (IOI15_boxes) C++14
0 / 100
 3 ms 8540 KB 
#include <iostream>
#include "boxes.h"
#define MAX_N 10000002


// We need to build array C - counts how many elements are in a certain position
// And array L, distance of all de different elements

int M;
int C[MAX_N], P[MAX_N], pos[MAX_N];
int first[MAX_N], last[MAX_N];
int summ[MAX_N];

int sum(int x, int y) {
    return summ[y] - summ[x];
}

long long delivery(int N, int K, int L, int p[]) {
    int prev = 0;
    int x = 0;
    
    for (int i = 0; i < N; i++) {
        if (p[i] == prev) {
            C[x]++;
        } else {
            x++;
            P[x] = p[i] - prev;
            pos[x] = p[i];
            C[x] = 1;
            prev = p[i];
        }
    }

    P[++x] = L - p[N - 1];
    M = x;
    for (int i = 1; i <= M; i++)
        summ[i] = summ[i - 1] + P[i];

    int mid = L/2;
    
    // op1
    long long totR = 0;
    long long costo;
    int i = 1;

    for (; i < M && pos[i] <= mid; i++) {
        first[i] = K - last[i - 1];
        if (first[i] >= C[i]) {
            costo = (long long)P[i];
            last[i] = first[i] - C[i];
        } else {
            costo = (long long)P[i] + 2 * (long long)sum(0, i) * (long long)((C[i] - first[i]) / K);
            last[i] = (C[i] - first[i]) % K; 
        }
        totR += costo;
        //printVal("f",first[i]);
        //printVal("costo",costo);
    }

    if (i < M && last[i]) {
        //printVal("hola", 00);
        int R = last[i];
        while (i < M) {
            totR += (long long)P[i];
            int q = std::min(C[i], R);
            C[i] -= q;
            R -= q;
        }
        totR += (long long)P[M];
    } else {
        i--;
        totR += sum(0, i);
        //printVal("hola", totR);
    }

    for (i = M - 1; i >= 0 && pos[i] > mid; i--) {
        first[i] = K - last[i + 1];
        if (first[i] >= C[i]) {
            costo = (long long)P[i];
            last[i] = first[i] - C[i];
        } else {
            costo = (long long)P[i] + 2 * (long long)sum(i, M) * (long long)((C[i] - first[i]) / K);
            last[i] = (C[i] - first[i]) % K; 
        }
        //printVal("f",first[i]);
        //printVal("c",costo);
        totR += costo;
    }

    i++;
    totR += (long long)sum(i, M);
    // op2
    //long long totL = 0;

    //return std::min(totR, totL);

    return totR;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -