Submission #1122447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122447		AnhPham	Fuel Station (NOI20_fuelstation)	C++20	67 / 100	3093 ms	14468 KiB

FuelStation

#include <bits/stdc++.h>

using namespace std;

#define int     long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()

const   int     MOD = (int)1e9 + 7;
const   int     INF = (int)4e18 + 18;

void solve();

int32_t main() {
#define CODE "task"
    if (fopen(CODE".inp", "r"))
        freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
    int testcases = 1;

#define multitest 0
    if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/**                            The Last Dance                            **/

struct FUELSTATION {
    int X, A, B;

    bool operator < (const FUELSTATION &other) const {
        return (X == other.X ? A < other.A : X < other.X);
    }
};

int N, D;
vector <FUELSTATION> stations;

namespace sub1 {
    bool check_condition() {
        return N == 1;
    }

    void solve() {
        cout << (max(stations[0].X, D - stations[0].A) <= stations[0].B ? max(stations[0].X, D - stations[0].A) : D) << '\n';
    }
}

namespace sub2 {
    bool check_condition() {
        for (auto item : stations)
            if (item.B != 1e9)
                return 0;

        return 1;
    }

    void solve() {
        stations.push_back({ 0, 0, 0 });
        stations.push_back({ D, 0, 0 });
        sort(all(stations));

        int ans = 0;
        int sum = 0;
        for (int i = 0; i < sz(stations); ++i) {
            ans = max(ans, stations[i].X - sum);
            sum += stations[i].A;
        }

        cout << ans << '\n';
    }
}

namespace sub356 {
    bool check_condition() {
        return N <= 1e4;
    }

    bool possible(int f) {
        int F = f;
        for (int i = 1; i < sz(stations); ++i) {
            f -= stations[i].X - stations[i - 1].X;

            if (f < 0)
                return 0;

            if (F > stations[i].B)
                continue;

            f += stations[i].A;
        }

        return 1;
    }

    void solve() {
        stations.push_back({ 0, 0, (int)1e9 });
        stations.push_back({ D, 0, (int)1e9 });
        sort(all(stations));

        vector <int> max_fuel = { D };
        for (auto item : stations)
            max_fuel.push_back(item.B);

        sort(all(max_fuel));
        int hi = D;
        for (auto d : max_fuel)
            if (possible(d)) {
                 hi = d;
                 break;
            }

        int ans = -1;
            int lo = 0;
            while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (possible(mid))
                ans = mid, hi = mid - 1;
            else
                lo = mid + 1;
        }

        cout << ans << '\n';
    }
}


void solve() {
    cin >> N >> D;

    stations = vector <FUELSTATION> (N);
    for (auto &item : stations)
        cin >> item.X >> item.A >> item.B;

//    if (sub1 :: check_condition())
//        sub1 :: solve();
//    else if (sub2 :: check_condition)
//        sub2 :: solve();
//    else if (sub356 :: check_condition())
        sub356 :: solve();
}

Compilation message (stderr)

FuelStation.cpp: In function 'int32_t main()':
FuelStation.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
FuelStation.cpp:17:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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