제출 #1237115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237115		ericl23302	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	9028 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pl pair<ll, ll>
#define pll pair<ll, pl>
#define ppl pair<pl, pl>

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
    int Q = E.size();
    std::vector<long long> R(Q, 0);

    int n = W.size();
    vector<pair<ll, pair<ll, ll>>> items(n);
    for (int i = 0; i < n; ++i) items[i] = {W[i], {A[i], B[i]}};
    sort(items.begin(), items.end());

    vector<ll> benefit(n);
    for (int i = 0; i < n; ++i) benefit[i] = items[i].second.first - items[i].second.second;

    int idx = 0;
    for (auto &d : E) {
        vector<pl> dp(n + 1, {LLONG_MAX / 2, LLONG_MAX / 2});
        dp[0] = {0, LLONG_MAX / 2};

        for (int i = 1; i <= n; ++i) {
            dp[i].second = min(dp[i - 1].first, dp[i - 1].second) + items[i - 1].second.first;
            dp[i].first = dp[i].second;
            if (i > 1 && items[i - 1].first - items[i - 2].first <= d) dp[i].first = min(dp[i].first, dp[i - 1].second - benefit[i - 2] + items[i - 1].second.second);
            if (i > 2 && items[i - 1].first - items[i - 3].first <= d) dp[i].first = min(dp[i].first, dp[i - 2].second - benefit[i - 3] + items[i - 2].second.first + items[i - 1].second.second);
        }

        R[idx++] = min(dp[n].first, dp[n].second);
    }

    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18