Submission #528323

#	Time	Username	Problem	Language	Result	Execution time	Memory
528323		Cyanmond	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	593 ms	371656 KiB

boxes

// clang-format off
#include "boxes.h"
#include <bits/stdc++.h>

using i64 = int64_t;

template <typename T = int> T scan() {
    T ret; std::cin >> ret;
    return ret;
}

long long solve(const int N, const int K, const int L, std::vector<int> P) {
    std::vector<i64> l_sum(N + 1), r_sum(N + 1);
    l_sum[0] = r_sum[N] = 0;
    for (int i = 0; i < K; ++i) {
        l_sum[i + 1] = std::min({L, 2 * (L - P[0]), 2 * P[i]});
    }
    for (int i = N; i > N - K; --i) {
        r_sum[i - 1] = std::min({L, 2 * P[N - 1], 2 * (L - P[i - 1])});
    }

    for (int i = K; i < N; ++i) {
        const int cost = std::min({L, 2 * P[i], 2 * (L - P[i - K + 1])});
        l_sum[i + 1] = l_sum[i - K + 1] + cost;
    }
    for (int i = N - K; i > 0; --i) {
        const int cost = std::min({L, 2 * (L - P[i - 1]), 2 * P[i + K - 2]});
        r_sum[i - 1] = r_sum[i + K - 1] + cost;
    }

    i64 answer = (i64)5000000000000000;
    for (int i = 0; i <= N; ++i) {
        answer = std::min(answer, l_sum[i] + r_sum[i]);
    }

    return answer;
}

long long delivery(int N, int K, int L, int P[]) {
    std::vector<int> vec(N);
    for (int i = 0; i < N; ++i) vec[i] = P[i];
    return solve(N, K, L, vec);
}

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