Submission #368002

#	Time	Username	Problem	Language	Result	Execution time	Memory
368002		KoD	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2096 ms	33516 KiB

boxes

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

#include <vector>
#include <algorithm>
#include <iostream>

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

constexpr long long INF = 1000000000000000000;

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> dp_l(L + 1), dp_r(R + 1);
    for (int i = 1; i <= L; ++i) {
        dp_l[i] = dp_l[(i >= K ? i - K : 0)] + 2 * left[i - 1];
    }
    for (int i = 1; i <= R; ++i) {
        dp_r[i] = dp_r[(i >= K ? i - K : 0)] + 2 * right[i - 1];
    }
    Vec<long long> dp(N + 1, INF);
    for (int i = 0; i <= L; ++i) {
        for (int j = 0; j <= R; ++j) {
            dp[i + j] = std::min(dp[i + j], dp_l[i] + dp_r[j]);
        }
    }
    long long ret = INF;
    for (int i = 0; i <= N; ++i) {
        const auto first = (long long) Len * ((N - i + K - 1) / K);
        const auto second = dp[i];
        ret = std::min(ret, first + second);
    }
    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: 0 / 20
• Subtask 6: 0 / 30