Submission #1286892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286892		MMihalev	Nile (IOI24_nile)	C++20	67 / 100	2094 ms	7848 KiB

nile

#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
#include "nile.h"
using namespace std;
const int MAX_N=1e5+5;
long long a[MAX_N];
long long b[MAX_N];
int w[MAX_N];
int n;

vector<int>v;
int d;
long long dp[MAX_N];
long long solve()
{
    for(int i=1;i<=v.size();i++)
    {
        int id=v[i-1];
        dp[i]=dp[i-1]+a[id];
        if(i>=2)
        {
            dp[i]=min(dp[i],dp[i-2]+b[id]+b[v[i-2]]);
        }
        if(i>=3)
        {
            if(w[id]-w[v[i-3]]<=d)
            {
                dp[i]=min(dp[i],dp[i-3]+b[id]+a[v[i-2]]+b[v[i-3]]);
            }
        }
    }
    return dp[v.size()];
}
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();
    vector<pair<int,int>>order;
    for(int i=0;i<n;i++)
    {
        a[i]=A[i];
        b[i]=B[i];
        w[i]=W[i];
        order.push_back({w[i],i});
    }
    sort(order.begin(),order.end());

    vector<long long>answers;
    for(int idquery=0;idquery<E.size();idquery++)
    {
        d=E[idquery];
        long long ans=0;

        v.clear();
        v.push_back(order[0].second);

        for(int i=1;i<n;i++)
        {
            if(order[i].first-order[i-1].first>d)
            {
                ans+=solve();
                v.clear();
            }
            v.push_back(order[i].second);
        }
        ans+=solve();

        answers.push_back(ans);
    }

    return answers;
}

• 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