DMOJ · cco14p4

Where's That Fuel?

This C++ solution uses greedy for DMOJ cco14p4 Where's That Fuel?. Read the reasoning, inspect the code, or try your own test case below.

cco14p4GreedyC++37 lines
Solution238of 248
Open official problem ↗ Download C++ file ↓ Search the library → Open full Code Lab ↗ Report an issue ↗

Approach

Greedy

Where's That Fuel? matches the starting planet, per-planet fuel/cost data, and the two greedy optimization outputs.

Greedy

Problem and code

Useful links.

Written by benbenyaojifen. Try the problem first, then compare your approach with the code.

Open official problem ↗View exact source file ↗
Implementation

P_4_Where_s_That_Fuel.cpp

C++

    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    const int inf = 1e9;
    const long long INF = 1e17; //❄️
    int main() {
        ios::sync_with_stdio(0); cin.tie(0); 
        int n, pos; cin >> n >> pos;
        vector<pair<int, int>> a;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            int get, cost; cin >> get >> cost;
            if (i + 1 == pos) {
                cur = get;
                continue;
            }
            if (get - cost < 0) continue;
            a.emplace_back(cost, get);
        }
        sort(a.begin(), a.end(), [&] (const pair<int, int> &x, const pair<int, int> &y) {
                if (x.first != y.first) return x.first < y.first;
                return x.second > y.second;
        });
        int cnt = 1;
        for (int i = 0; i < a.size(); i++) {
            if (cur >= a[i].first) {
                cur -= a[i].first;
                cur += a[i].second;
                cnt++;
            } else {
                break;
            }
        }
        cout << cur << '\n';
        cout << cnt << '\n';
        return 0;
    }
        

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗Keep studying →

Test this problem

Run your code here.

Paste your code, run a test case, compare the output, or trace selected values.

Full trace, comparison & stress testing ↗
StatusReady
Output
No run yet.
Diagnostics
No diagnostics yet.

Each run is isolated and has strict limits. Passing one test does not guarantee the judge will accept the solution.