제출 #1304359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304359		TroySer	나일강 (IOI24_nile)	C++20	23 / 100	2094 ms	15156 KiB

nile

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

using namespace std;
using ll = long long;

const ll INF = 9e18;

struct Artifact {
    ll w;
    ll a;
    ll b;
};

const ll MAX_SZ = 1e5 + 10;
ll memo[MAX_SZ];

ll dp(ll ind, ll D, vector<Artifact> &artifacts) {

    ll N = (ll)artifacts.size();
    
    if (ind == N) return 0;
    if (memo[ind] != -1LL) {
        return memo[ind];
    }

    ll res1 = dp(ind + 1, D, artifacts) + artifacts[ind].a;
    ll res2 = INF;
    if (ind != N - 1 && abs(artifacts[ind].w - artifacts[ind + 1].w) <= D) {
        res2 = dp(ind + 2, D, artifacts) + artifacts[ind].b + artifacts[ind + 1].b;
    }

    return memo[ind] = min(res1, res2);

}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {

    ll Q = (ll)E.size();
    ll N = (ll)A.size();

    vector<ll> R(Q);
    
    vector<Artifact> artifacts;
    artifacts.reserve(N);
    for (ll i = 0; i < N; i++) {
        artifacts.push_back(Artifact{W[i], A[i], B[i]});
    }

    sort(artifacts.begin(), artifacts.end(), [&](Artifact &a, Artifact &b) {
        if (a.w == b.w) {
            return a.a - a.b < b.a - b.b;
        }
        return a.w < b.w;
    });
    
    for (ll queryInd = 0; queryInd < Q; queryInd++) {

        memset(memo, -1LL, sizeof(memo));

        ll res = dp(0, E[queryInd], artifacts);
        R[queryInd] = res;

    }

    return R;

}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 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