제출 #1277715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277715		aryan	Fuel Station (NOI20_fuelstation)	C++20	7 / 100	3094 ms	9568 KiB

FuelStation

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){

    int n,d;
    cin >> n >> d;
    vector<int> x(n),a(n),b(n);
    for(int i = 0;i < n;i++){
        cin >> x[i] >> a[i] >> b[i];
    }   
    vector<int> ind(n);
    iota(ind.begin(),ind.end(),0);
    sort(ind.begin(),ind.end(),[&](int i,int j){
        return x[i] < x[j];
    });

    vector<int> ind2(n);
    iota(ind2.begin(),ind2.end(),0);
    sort(ind2.begin(),ind2.end(),[&](int i,int j){
        return b[i] < b[j];
    });

    vector<i64> pref(n + 1);
    i64 tot = 0;
    vector<int> hs(n);
    for(int i = 0;i < n;i++){
        int e = ind[i];
        hs[e] = i;
        if(i) pref[i] = pref[i - 1] - (x[e] - x[ind[i - 1]]) + a[ind[i - 1]]; 
        else pref[i] = -x[e];
        // cout << e << " " << pref[i] << '\n';
        tot = max(tot,-1LL * pref[i]);
    }
    pref[n] = pref[n - 1] - (d - x[ind[n - 1]]) + a[ind[n - 1]]; 
    tot = max(tot,-1LL * pref[n]);
    i64 f = d;
    if(tot <= b[ind2[0]]){
        f = tot;
    }

    for(int i = 0;i < n;i++){
        // f is between (b[i] to b[i + 1]];
        int e = ind2[i];    
        int e2 = hs[e];
        // removig b[e]
        i64 my = 0;
        for(int j = e2 + 1;j <= n;j++){
            pref[j] -= a[e];
        }
        for(int j = 0;j <= n;j++){
            my = max(my,-1LL * pref[j]);
        }
        if((i ? b[ind2[i - 1]] : -1) < my <= (i + 1 < n ? b[ind2[i + 1]] : d)){
            f = min(f,my);
        }
    }
    cout << f << '\n';

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 12
• Subtask 5: 0 / 19
• Subtask 6: 0 / 11
• Subtask 7: 0 / 21