oj.uz

Submission #238028

# Submission time Handle Problem Language Result Execution time Memory
238028 2020-06-09T18:57:15 Z Kubin Boxes with souvenirs (IOI15_boxes) C++11
35 / 100
 5 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

long long delivery(int _n, int _k, int l, int p[])
{
    size_t n = _n, k = _k;
    vector<int> A[2]; int a = 0;
    A[0].reserve(n); A[1].reserve(n);
    for(size_t i = 0; i < n; i++) if(p[i])
    {
        if(2*p[i] == l)      a++;
        else if(p[i] <= l/2) A[0].push_back(p[i]);
        else                 A[1].push_back(l - p[i]);
    }
    reverse(A[1].begin(), A[1].end());

    vector<int64_t> B[2];
    for(size_t t = 0; t < 2; t++)
    {
        B[t].resize(A[t].size() + a + 1);
        for(size_t i = 0; i < A[t].size() + a; i++)
            B[t][i+1] = (i+1 >= k ? B[t][i+1-k] : 0) + (i<A[t].size() ? A[t][i] : l/2);
    }

    size_t ni = a + A[0].size() + A[1].size();
    int64_t result = ni ? INT64_MAX : 0, base = 0;
    while(ni)
    {
        for(int x = 0; x <= a; x++)
        {
            result = min(
                result,
                base + 2 * (B[0][A[0].size() + size_t(x)]
                          + B[1][A[1].size() + size_t(a-x)])
            );
        }

        for(size_t i = 0; i < k and ni; i++, ni--)
        {
            if(a)                   a--;
            else if(A[0].empty())   A[1].pop_back();
            else if(A[1].empty())   A[0].pop_back();
            else
            {
                auto d0 = B[0][A[0].size()] - B[0][A[0].size() - 1],
                     d1 = B[1][A[1].size()] - B[1][A[1].size() - 1];
                if(d0 < d1) A[1].pop_back();
                else        A[0].pop_back();
            }
        }
        base += l;
    }
    result = min(result, base);

    return result;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 4 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 464 KB Output is correct
25 Correct 5 ms 256 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Incorrect 4 ms 384 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 4 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 464 KB Output is correct
25 Correct 5 ms 256 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Incorrect 4 ms 384 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 4 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 464 KB Output is correct
25 Correct 5 ms 256 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Incorrect 4 ms 384 KB Output isn't correct
28 Halted 0 ms 0 KB -