제출 #1309384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309384		trigon	나일강 (IOI24_nile)	C++20	17 / 100	2095 ms	6188 KiB

nile

#include <bits/stdc++.h>
using namespace std;

struct Artifact {
    int weight, A, B;
};

vector<long long> calculate_costs(
    vector<int> W, vector<int> A, vector<int> B, vector<int> E) 
{
    int N = W.size();
    int Q = E.size();

    // Build artifacts
    vector<Artifact> artifacts(N);
    for (int i = 0; i < N; i++) {
        artifacts[i] = {W[i], A[i], B[i]};
    }

    // Sort artifacts by weight
    sort(artifacts.begin(), artifacts.end(), [](const Artifact &a, const Artifact &b){
        return a.weight < b.weight;
    });

    // Answers vector
    vector<long long> answers(Q);

    for (int q_idx = 0; q_idx < Q; q_idx++) {
        int D = E[q_idx];
        vector<long long> dp(N + 1, LLONG_MAX);
        dp[0] = 0; // cost of transporting 0 artifacts is 0

        for (int i = 0; i < N; i++) {
            // Option 1: send i-th artifact alone
            dp[i + 1] = min(dp[i + 1], dp[i] + artifacts[i].A);

            // Option 2: pair i-th with (i+1)-th if allowed
            if (i + 1 < N && abs(artifacts[i + 1].weight - artifacts[i].weight) <= D) {
                dp[i + 2] = min(dp[i + 2], dp[i] + artifacts[i].B + artifacts[i + 1].B);
            }
        }

        answers[q_idx] = dp[N];
    }

    return answers;
}

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