Submission #368042

#	Time	Username	Problem	Language	Result	Execution time	Memory
368042		KoD	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	674 ms	190956 KiB

boxes

#ifndef LOCAL
#include "boxes.h"
#endif

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>

template <class T>
using Vec = std::vector<T>;

constexpr long long INF = std::numeric_limits<long long>::max();

long long delivery(int N, int K, int Len, int P[]) {
    Vec<int> left, right;
    left.reserve(N);
    right.reserve(N);
    for (int i = 0; i < N; ++i) {
        const auto l = P[i];
        const auto r = Len - P[i];
        if (l <= r) {
            left.push_back(l);
        }
        else {
            right.push_back(r);
        }
    } 
    std::reverse(right.begin(), right.end());
    const int L = (int) left.size();
    const int R = (int) right.size();
    Vec<long long> memo(K);
    for (int i = 0; i < R; ++i) {
        memo[i % K] += std::min(Len, 2 * right[i]);
    }
    Vec<long long> sum(K);
    long long ret = INF;
    for (int i = 0; i <= L; ++i) {
        const auto over = ((L - i) + (K - 1)) / K;
        const auto remain = (N - i) - K * over;
        ret = std::min(ret, (i == 0 ? 0 : sum[(i - 1) % K]) + (long long) Len * over + (remain <= 0 ? 0 : memo[(remain - 1) % K]));
        if (i != L) {
            sum[i % K] += 2 * left[i];
        }
    }
    return ret;
}

#ifdef LOCAL 
int main() {
    int N, K, L;
    std::cin >> N >> K >> L;
    int P[100] = {};
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i];
    }
    std::cout << delivery(N, K, L, P) << '\n';
    return 0;
}
#endif

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