Submission #519681

#	Time	Username	Problem	Language	Result	Execution time	Memory
519681		KoD	Holding (COCI20_holding)	C++17	110 / 110	154 ms	4408 KiB

holding

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;
constexpr ll inf = std::numeric_limits<ll>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, L, R, K;
    std::cin >> N >> L >> R >> K;
    L -= 1;
    vector dp(R - L + 1, vector(K + 1, inf));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        for (int j = R - L - 1; j >= 0; --j) {
            for (int k = K; k >= 0; --k) {
                const int d = std::abs(i - (j + L));
                if (k + d <= K) {
                    dp[j + 1][k + d] = std::min(dp[j + 1][k + d], dp[j][k] + a);
                }
            }
        }
    }
    std::cout << *std::min_element(dp[R - L].begin(), dp[R - L].end()) << '\n';
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22