oj.uz

Submission #337073

# Submission time Handle Problem Language Result Execution time Memory
337073 2020-12-18T06:10:38 Z blue Boxes with souvenirs (IOI15_boxes) C++11
0 / 100
 1 ms 384 KB 
#include "boxes.h"
#include <iostream>
using namespace std;

//#teams, capacity, #sections, position of each team
long long delivery(int N, int K, int L, int positions[])
{
    long long dp_inc[N]; //minimum time needed to cover all 0, 1, ... i and end up at positions[[i]

    dp_inc[0] = min(positions[0], L - positions[0]);
    for(int i = 1; i < N; i++)
    {
        if(i % K == 0)
        {
            dp_inc[i] = dp_inc[i-1] + min(positions[i-1], L - positions[i-1]) + min(positions[i], L - positions[i]);
        }
        else
        {
            dp_inc[i] = dp_inc[i-1] + (positions[i] - positions[i-1]);
        }
    }

    long long dp_dec[N];
    int last0 = -1;

    for(int i = 0; i < N && positions[i] == 0; i++)
    {
        dp_dec[i] = 0;
        last0 = i;
    }

    dp_dec[N-1] = min(positions[N-1], L - positions[N-1]);
    for(int i = N-2; i > last0; i--)
    {
        if((N - 1 - i) % K == 0)
        {
            dp_dec[i] = dp_dec[i+1] + min(positions[i+1], L - positions[i+1]) + min(positions[i], L - positions[i]);
        }
        else
        {
            dp_dec[i] = dp_dec[i+1] + (positions[i+1] - positions[i]);
        }
    }

    long long res = (long long)(1000 * 1000 * 1000) * (long long)(1000 * 1000 * 1000);
    for(int i = 0; i < N; i++)
        res = min(res, dp_inc[i] + dp_dec[i+1] + min(positions[i], L - positions[i]) + min(positions[i+1], L - positions[i+1]));

    return res;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 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 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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