Submission #1230952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230952		sahasrad	Nile (IOI24_nile)	C++20	67 / 100	2093 ms	15256 KiB

nile

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

typedef long long ll;
typedef pair<int, ll> pil;

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<vector<int>> arr(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        arr[i][0] = W[i];
        arr[i][1] = A[i];
        arr[i][2] = B[i];
    }

    sort(arr.begin(), arr.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    vector<ll> ans(q);
    for (int qi = 0; qi < q; qi++) {
        int d = E[qi];
        ll sum = 0;
        vector<ll> dp(n);
        queue<pil> q;
        multiset<ll> qVal;

        for (int i = 0; i < n; i++) {
            int w = arr[i][0], a = arr[i][1], b = arr[i][2];
            while (!q.empty() && q.front().first < w - d) {
                auto [w2, val] = q.front();
                q.pop();
                qVal.erase(qVal.find(val));
            }
            ll last = i == 0 ? 0 : dp[i - 1];
            dp[i] = last + a;
            if (!q.empty()) {
                dp[i] = min(dp[i], *qVal.begin() + sum + b);
            }
            sum += a;
            ll val = last + b - sum;
            q.push({w, val});
            qVal.insert(val);
        }

        ans[qi] = dp[n - 1];
    }

    return ans;
}

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int n, q;
//     cin >> n >> q;
//     vector<int> W(n), A(n), B(n), E(q);
//     for (int i = 0; i < n; i++) {
//         cin >> W[i];
//     }
//     for (int i = 0; i < n; i++) {
//         cin >> A[i];
//     }
//     for (int i = 0; i < n; i++) {
//         cin >> B[i];
//     }
//     for (int i = 0; i < q; i++) {
//         cin >> E[i];
//     }

//     vector<ll> result = calculate_costs(W, A, B, E);
//     for (ll cost : result) {
//         cout << cost << "\n";
//     }
//     return 0;
// }

• 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