Submission #1170746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170746		Zakir060	Nile (IOI24_nile)	C++20	Compilation error	0 ms	0 KiB

nile

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;
const ll NEG_INF = -1e18;

// Structure for an artifact.
struct Artifact {
    int w, A, B, s; // weight, solo cost, paired cost, saving = A - B
};

// Segment Tree for range maximum queries.
struct SegTree {
    int n;
    vector<ll> tree;

    SegTree(int n_) : n(n_) {
        tree.assign(4*n, NEG_INF);
    }

    void update(int idx, int l, int r, int pos, ll val) {
        if (l == r) {
            tree[idx] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid)
            update(2*idx, l, mid, pos, val);
        else
            update(2*idx+1, mid+1, r, pos, val);
        tree[idx] = max(tree[2*idx], tree[2*idx+1]);
    }

    ll query(int idx, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return NEG_INF;
        if (ql <= l && r <= qr) return tree[idx];
        int mid = (l + r) / 2;
        return max(query(2*idx, l, mid, ql, qr),
                   query(2*idx+1, mid+1, r, ql, qr));
    }

    void update(int pos, ll val) {
        update(1, 0, n-1, pos, val);
    }

    ll query(int l, int r) {
        if(l > r) return NEG_INF;
        return query(1, 0, n-1, l, r);
    }
};

// Compute the answer for one query with given D.
ll computeAnswer(const vector<Artifact>& artifacts, ll base, int D) {
    int n = artifacts.size();
    // dp[i] = maximum total saving using artifacts 0..i (in sorted order)
    vector<ll> dp(n, 0);
    // X[j] = (if j == 0 then s[0] else dp[j-1] + s[j])
    vector<ll> X(n, 0);
    // Build segment tree over indices [0, n-1] for X values.
    SegTree seg(n);

    // For artifact 0:
    dp[0] = 0;  // cannot pair artifact0 alone
    X[0] = artifacts[0].s; // (dp[-1] assumed 0)
    seg.update(0, X[0]);

    // For artifacts 1 to n-1:
    for (int i = 1; i < n; i++) {
        // Find L: the first index with weight >= artifacts[i].w - D.
        int low = 0, high = i;
        int L = i; // default: no candidate
        while(low < high) {
            int mid = (low + high) / 2;
            if (artifacts[mid].w >= artifacts[i].w - D)
                high = mid;
            else
                low = mid + 1;
        }
        L = low;
        ll candidate = NEG_INF;
        if (L <= i-1 && artifacts[i].w - artifacts[L].w <= D) {
            candidate = artifacts[i].s + seg.query(L, i-1);
        }
        dp[i] = max(dp[i-1], candidate);

        // Set X[i] = dp[i-1] + s[i] (artifact i remains free to be paired later if not paired now)
        X[i] = dp[i-1] + artifacts[i].s;
        seg.update(i, X[i]);
    }
    // Minimum total cost = base cost - total saving
    return base - dp[n-1];
}

// Main procedure to answer Q queries.
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size();
    int Q = E.size();
    vector<ll> ans(Q, 0);

    // Build artifacts vector.
    vector<Artifact> artifacts(n);
    ll base = 0;
    for (int i = 0; i < n; i++) {
        artifacts[i].w = W[i];
        artifacts[i].A = A[i];
        artifacts[i].B = B[i];
        artifacts[i].s = A[i] - B[i];
        base += A[i];
    }
    // Sort artifacts by weight.
    sort(artifacts.begin(), artifacts.end(), [](const Artifact& a, const Artifact& b) {
        return a.w < b.w;
    });

    // For each query, run the DP.
    // (Note: This is O(n log n) per query. For worst-case constraints further offline processing is needed.)
    for (int j = 0; j < Q; j++) {
        ans[j] = computeAnswer(artifacts, base, E[j]);
    }
    return ans;
}

// Sample main to test the sample test-case.
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> W(N), A(N), B(N);
    for (int i = 0; i < N; i++){
        cin >> W[i] >> A[i] >> B[i];
    }
    int Q;
    cin >> Q;
    vector<int> E(Q);
    for (int j = 0; j < Q; j++){
        cin >> E[j];
    }

    vector<ll> R = calculate_costs(W, A, B, E);
    for (auto &val : R)
        cout << val << "\n";

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccRcbnYH.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccR7IBIr.o:nile.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status