Submission #1364464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364464		eradax	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	4952 KiB

nile

#pragma GCC optimize("O3")
#include<bits/allocator.h>
#pragma GCC target("avx2")
#include"nile.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    int n=ssize(W),q=ssize(E);

    vector<array<int,3>> a(n);
    for(int i=0;i<n;i++)a[i]={W[i],A[i],B[i]};
    sort(begin(a),end(a));

    vector<ll> res;

    if(n<=1){
        res.insert(begin(res),q,a[0][1]);
        return res;
    }

    for(int d:E){
        ll ppu,pu,pm;

        ppu=a[0][2]+a[1][1];
        pu=a[0][1]+a[1][2];
        pm=(a[1][0]-a[0][0]<=d)?a[0][2]+a[1][2]:a[0][1]+a[1][1];
        for(int i=2;i<n;i++){
            ll cu=1e18,cm=1e18;

            cu=pm+a[i][2];
            cm=pm+a[i][1];
            if(a[i][0]-a[i-1][0]<=d)cm=min(cm,pu+a[i][2]);
            if(a[i][0]-a[i-2][0]<=d)cm=min(cm,ppu+a[i][2]);

            ppu=pu+a[i][1];
            pu=cu;
            pm=cm;
        }

        res.push_back(pm);
    }
    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