Submission #1305452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305452		1ota	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	7480 KiB

nile

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

#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

const int inf = 9e18;

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> qn){
    int n = (ll) A.size(), q = (ll) qn.size();
    vector<pii> a(n);
    for (int i = 0; i < n; i++) a[i] = pii{W[i], A[i] - B[i]};
    sort(entire(a));

    ll base = accumulate(entire(B), 0ll), oth = 0;
    for (auto [w, c] : a) oth += c;
    vector<ll> r(q);

    for (int quer = 0; quer < q; quer++){
        ll d = qn[quer];
        vector<ll> dp(n, 0), pref(n, 0); 

        for (int i = 1; i < n; i++){
            dp[i] = pref[i-1];
            if (a[i].ff - a[i-1].ff <= d) dp[i] = max(dp[i], a[i].ss + a[i-1].ss + dp[max(0, i-2)]);
            if (i > 1 and a[i].ff - a[i-2].ff <= d) dp[i] = max(dp[i], a[i].ss + a[i-2].ss + dp[max(0, i-3)]);
            pref[i] = max(pref[i-1], dp[i]);
        }
        r[quer] = base + oth - pref[n-1];
    }

    return r;
}

Compilation message (stderr)

nile.cpp:11:17: warning: overflow in conversion from 'double' to 'int' changes value from '9.0e+18' to '2147483647' [-Woverflow]
   11 | const int inf = 9e18;
      |                 ^~~~

• 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