Submission #1256930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256930		nerrrmin	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	7104 KiB

nile

#include "nile.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int n, q;
long long w[maxn], a[maxn], b[maxn];

long long dp[maxn]; /// best match count
long long solve(int d)
{
    dp[0] = a[0];
    for (int i = 1; i < n; ++ i)
        dp[i] = dp[i-1] + a[i];

    for (int i = 1; i < n; ++ i)
    {
       long long best = dp[i];

        long long sumbs = 0, bestb = 1e17;
        for (int j = i-1; j >= 0; -- j)
        {
            if(w[i] - w[j] <= d)
            {
                best = min(best, dp[j-1] + b[i] + b[j] + sumbs + (i - j - 1)%2 * bestb);
            }
            else break;
            sumbs += b[j];
            bestb = min(bestb, a[j] - b[j]);
        }
        dp[i] = min(dp[i-1] + a[i], best);
    }

    return (dp[n-1]);
}

struct p
{
    int w, a, b;
    p(){};
    p(int _w, int _a, int _b)
    {
        w = _w;
        a = _a;
        b = _b;
    }
};

bool cmp(p p1, p p2)
{
    return (p1.w < p2.w);
}
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 = 0; i < n; ++ i)
        w[i] = W[i];
    for (int i = 0; i < n; ++ i)
        a[i] = A[i];
    for (int i = 0; i < n; ++ i)
        b[i] = B[i];
    vector < p > g;
    for (int i = 0; i < n; ++ i)
        g.pb(p(w[i], a[i], b[i]));
    sort(g.begin(), g.end(), cmp);
    int i = 0;
    for (auto &[ww, aa, bb]: g)
    {

        w[i] = ww;
        a[i] = aa;
        b[i] = bb;
        i ++;
    }

    q = (int)E.size();
    vector < long long > res;
    for (auto d: E)
    {
        res.pb(solve(d));
    }
    return res;
}

• 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