Submission #238023

#	Time	Username	Problem	Language	Result	Execution time	Memory
238023		Kubin	Boxes with souvenirs (IOI15_boxes)	C++11	15 / 100	7 ms	640 KiB

boxes

#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() + 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[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 if(A[0].back() < A[1].back())  A[1].pop_back();
            else                                A[0].pop_back();
        }
        base += l;
    }
    result = min(result, base);

    return result;
}

#ifdef XHOVA
namespace grader
{
    static char _buffer[1024];
    static int _currentChar = 0;
    static int _charsNumber = 0;
    static FILE *_inputFile, *_outputFile;

    static inline int _read() {
        if (_charsNumber < 0) {
            exit(1);
        }
        if (!_charsNumber || _currentChar == _charsNumber) {
            _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
            _currentChar = 0;
        }
        if (_charsNumber <= 0) {
            return -1;
        }
        return _buffer[_currentChar++];
    }

    static inline int _readInt() {
        int c, x, s;
        c = _read();
        while (c <= 32) c = _read();
        x = 0;
        s = 1;
        if (c == '-') {
            s = -1;
            c = _read();
        }
        while (c > 32) {
            x *= 10;
            x += c - '0';
            c = _read();
        }
        if (s < 0) x = -x;
        return x;
    }
    int main() {
    	_inputFile = fopen("boxes.in", "rb");
    	// _outputFile = fopen("boxes.out", "w");
        _outputFile = stdout;

        int N, K, L, i;
        N = _readInt();
        K = _readInt();
        L = _readInt();

        int *p = (int*)malloc(sizeof(int) * (unsigned int)N);

        for (i = 0; i < N; i++) {
            p[i] = _readInt();
        }

        fprintf(_outputFile, "%lld\n", delivery(N, K, L, p));

        free(p);

        return 0;
    }
}
int main() { return grader::main(); }
#endif

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30