Submission #1181674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181674		12345678	Nile (IOI24_nile)	C++20	67 / 100	2092 ms	6788 KiB

nile

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

using namespace std;

#define ll long long

const int nx=1e5+5;

struct info
{
    ll w, a, b;
    info(ll w=0, ll a=0, ll b=0): w(w), a(a), b(b){}
    bool operator< (const info &o) const {return w<o.w;}
} d[nx];

ll n, dp[nx];
vector<ll> res;

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
    n=W.size();
    for (int i=1; i<=n; i++) d[i]=info(W[i-1], A[i-1], B[i-1]);
    sort(d+1, d+n+1); 
    for (int t=0; t<E.size(); t++)
    {
        for (int i=1; i<=n; i++)
        {
            dp[i]=dp[i-1]+d[i].a;
            if (i>1&&d[i].w-d[i-1].w<=E[t]) dp[i]=min(dp[i], dp[i-2]+d[i].b+d[i-1].b);
            if (i>2&&d[i].w-d[i-2].w<=E[t]) dp[i]=min(dp[i], dp[i-3]+d[i-2].b+d[i-1].a+d[i].b);
        }
        res.push_back(dp[n]);
    }
    return res;
}

• 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