Submission #1231662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231662		Ghulam_Junaid	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	7872 KiB

nile

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

#define F first
#define S second

typedef long long ll;

const int N = 1e5 + 10;
int n, q;
ll dp[N];
vector<int> w, a, b, e;
vector<ll> ans;

vector<ll> calculate_costs(vector<int> ww, vector<int> aa, vector<int> bb, vector<int> ee) {
    n = (int)ww.size(), q = (int)ee.size();
    w = ww, a = aa, b = bb, e = ee;
    ans.resize(q, 0);

    vector<pair<int, pair<int, int>>> vec;
    for (int i = 0; i < n; i ++)
        vec.push_back({w[i], {a[i], b[i]}});
    sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i ++)
        w[i] = vec[i].F, a[i] = vec[i].S.F, b[i] = vec[i].S.S;

    for (int id = 0; id < q; id ++){
        int d = e[id];
        dp[0] = a[0];
        for (int i = 1; i < n; i ++){
            dp[i] = a[i] + dp[i - 1];
            if (w[i] - w[i - 1] <= d){
                ll last = 0;
                if (i > 1) last = dp[i - 2];
                dp[i] = min(dp[i], b[i] + b[i - 1] + last);
            }
            if (i > 1 and w[i] - w[i - 2] <= d){
                ll last = 0;
                if (i > 2) last = dp[i - 3];
                dp[i] = min(dp[i], (ll)b[i] + (ll)a[i - 1] + (ll)b[i - 2] + last);
            }
        }
        ans[id] = dp[n - 1];
    }
    return ans;
}

• 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