Submission #1299438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299438		chaitanyamehta	Fuel Station (NOI20_fuelstation)	C++20	0 / 100	2116 ms	7232 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);
    // cout<<solve();


    int total = (1 << n);
    int ans = 0 , fuel = 0 , curr = 0 , best = LLONG_MAX;
    for(int mask = 0 ;mask < total ;mask++){
        ans = 0, curr = 0, fuel = 0;
        for(int k = 0 ; k < n; k++){
            if(mask & (1 << k)){
                int req = w[k].x - curr;
                if(fuel < req){
                    ans += (req - fuel);
                    fuel += (req - fuel);
                }
                fuel -= req;
                fuel+=w[k].a;
                curr = w[k].x;
            }
        }
        bool ok = true;
        for(int k = 0 ; k < n; k++){
            if(mask & (1 << k)){
                if(w[k].b < ans){
                    ok = false;
                }
            }
        }
        // if(mask == 1){
        //     cout<<fuel <<"  "<<ans << " " << curr << "\n";
        // }
        int d = D - curr;
        if(fuel < d){
            ans+= D - curr;
        }
        if(ok){
            best = min(best , ans);
        }        
        
    }
    cout<<best;
}

• Subtask 1: 0 / 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