Taxi.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

long cars(vector<long long> x, long long m, long long d)
{
    sort(x.begin(), x.end(), greater<long long>());

    // find the worst car that can get us from taxipark to airport
    long lcar = -1;
    for (long i = 0; i < x.size() && x[i] >= m - d; i++)
    {
        lcar = i;
    }

    // exit if there is no such car
    if (lcar == -1)
    {
        return 0;
    }

    long min = 0;
    long long p = 0;
    for (long i = 0; i < x.size() && p < d; i++)
    {
        // check if we can get to the airport right now using lcar
        if (p + x[lcar] - (d - p) >= m && m > d)
        {
            return min + 1;
        }

        if (i != lcar || m == d)
        {
            // check if car[i] can actually reach us
            if (x[i] <= d - p) return 0;

            p = p + x[i] - (d - p);
            ++min;
        }
    }

    // if we are already in the airport
    if (p >= m)
    {
        return min;
    }

    // if we got to the taxipark, use lcar to get to the airport
    if (p >= d)
    {
        return min + 1;
    }

    return 0;
}


// not working for some reason :(
int main()
{
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);

    long long m, d;
    long n;
    cin >> m >> d >> n;
    vector<long long> x(n);
    for (long long i = 0; i < n; i++)
    {
        cin >> x[i];
    }

    long c = cars(x, m, d);
    cout << c;

    return 0;
}