Submission #1117987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117987		cpdreamer	Nile (IOI24_nile)	C++17	67 / 100	2067 ms	13808 KiB

nile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair
#define S second
#define F first
#define all(v) v.begin(),v.end()
#define V vector
#define pb push_back
const ll MOD=998244353;
struct artif{
    int w;
    int a;
    int b;
};
bool sorted(artif a,artif b){
    return a.w<b.w;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,std::vector<int> B, std::vector<int> E){
    V<long long>R;
    for(auto u:E) {
        int d=u;
        int n = (int) A.size();
        V<artif> vp;
        for(int i=0;i<n;i++)
            vp.pb({W[i],A[i],B[i]});
        sort(all(vp), sorted);
        V<V<artif>> vp1;
        vp1.pb({vp[0]});
        ll ans=0;
        for (int i = 1; i < n; i++) {
            int size=(int)vp1.size();
            int last=prev(vp1[size-1].end())->w;
            if(vp[i].w-last<=d){
                vp1[size-1].pb(vp[i]);
            }
            else{
                vp1.pb({vp[i]});
            }
        }
        for(auto v:vp1){
            ll s=0;
            for(auto x:v){
                s+=x.b;
            }
            if((int)v.size()%2==0){
                ans+=s;
            }
            else{
                ll c=LLONG_MAX;
                for(int i=0;i<(int)v.size();i++){
                    if(i%2==0){
                        c=min(c,s-v[i].b+v[i].a);
                    }
                    else{
                        if(v[i+1].w-v[i-1].w<=d){
                            c=min(c,s-v[i].b+v[i].a);
                        }
                    }
                }
                ans+=c;
            }
        }
        R.pb(ans);
    }
    return R;
}

• 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