Submission #1235406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235406		hugo_pm	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	11324 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = signed;

struct Query {
    int dis, id_qry;
    auto operator<=>(const Query&) const = default;
};
struct Artifact {
    int weight, value;
    auto operator<=>(const Artifact&) const = default;
};

int solve(const vector<Artifact> &arts, int dis) {
    int nb_arts = arts.size();
    vector<int> dp(nb_arts+1, 0);
    deque<Artifact> stk;
    for (int i = nb_arts-1; i >= 0; --i) {
        dp[i] = dp[i+1];
        while (!stk.empty() && stk.front().weight - arts[i].weight > dis)
            stk.pop_front();
        if (!stk.empty())
            dp[i] = max(dp[i], arts[i].value + stk.front().value);
        int add = arts[i].value + dp[i+1];
        while (!stk.empty() && stk.back().value <= add)
            stk.pop_back();
        stk.push_back({arts[i].weight, add});
    }
    return dp[0];
}

vector<int> solve(vector<Artifact> artifacts, vector<Query> queries) {
    vector<int> answer(queries.size(), 0);
    sort(artifacts.begin(), artifacts.end());
    sort(queries.begin(), queries.end());
    for (auto [dis, id_qry] : queries) {
        answer[id_qry] = solve(artifacts, dis);
    }
    return answer;
}

vector<int> calculate_costs(vector<i32> W, vector<i32> A, vector<i32> B, vector<i32> E) {
    int nb_artifacts = W.size(), nb_queries = E.size();
    vector<Artifact> artifacts;
    for (int i = 0; i < nb_artifacts; ++i) {
        artifacts.push_back({W[i], A[i] - B[i]});
    }
    vector<Query> queries;
    for (int i = 0; i < nb_queries; ++i) {
        queries.push_back({E[i], i});
    }
    vector<int> answer = solve(artifacts, queries);
    int sum_A = accumulate(A.begin(), A.end(), 0ll);
    for (int &x : answer) {
        x = sum_A - x;
    }
    return answer;
}

• 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