Submission #1222444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222444		LucaIlie	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	5132 KiB

nile

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

using namespace std;

struct aaa {
    int w, a, b;
};

const int MAX_N = 1e5;
long long dp[MAX_N + 1];
aaa v[MAX_N + 1];

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();
    vector<long long> ans(q);

    for (int i = 0; i < n; i++) 
      v[i + 1] = {w[i], a[i], b[i]};

    sort(v + 1, v + 1 + n, [](aaa x, aaa y) {
        return x.w < y.w;
    });

    for (int j = 0; j < q; j++) {
        int d = e[j];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + v[i].a;
            long long s = 0;
            for (int j = i - 1; j >= 1 && v[i].w - v[j].w <= d; j--) {
                dp[i] = min(dp[i], dp[j - 1] + v[i].b + v[j].b + s);
                s += v[j].a;
            }
        }
        ans[j] = dp[n];
    }

    return ans;
}

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