Submission #1299405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299405		chaitanyamehta	Fuel Station (NOI20_fuelstation)	C++20	37 / 100	3096 ms	7260 KiB

FuelStation

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

#define int long long 
int n , D;

struct Station{
    int x ,a  , b;
};
vector<Station> w;
bool cmp(Station u , Station v){
    if(u.x != v.x){
        return u.x < v.x;
    }
    else if(u.b != v.b){
        return u.b>v.b;
    }
    else{
        return u.a > v.a;
    }
}

bool check(int f){
    int fuel = f;
    int curr = 0;
    for(int i =0 ; i < n ;i ++){
        int d =w[i].x - curr;
        if(fuel < d){
            return false;
        }
        if(f <= w[i].b){
            fuel -= d;
            fuel += w[i].a;
            curr = w[i].x;
        }
    }
    int d = D - curr;
    if(fuel < d){
        return false;
    }

    return true;
}

int solve(){
    int l = 0, h = D , ans = LLONG_MAX/4;
    for(int i = 0; i <= D ; i++){
        if(check(i)){
            ans = i;
            break;
        }
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    cin>>n>>D;
    w.resize(n);
    for(int i = 0 ; i < n ;i++){
        cin>>w[i].x>>w[i].a>>w[i].b;
    }
    sort(w.begin() , w.end() , cmp);
    // for(int i = 0 ; i < n ;i++){
    //     cout<<w[i].x << " " << w[i].a << " " << w[i].b<<"\n";
    // }
    cout<<solve();
}

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