ACM ICPC 2011 WF - F. MACHINE WORKS - NOT DONE YET

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

struct machine {
    int day, price, resale, money_per_day;

    void read() {
        cin >> day >> price >> resale >> money_per_day;
    }

    bool operator < (const machine &A) const {
        return price < A.price;
    };
};

struct sol {
    int start, money_per_day;
    int64 prev_money;

    sol(int s, int m, int64 p) {
        start = s, money_per_day = m, prev_money = p;
    }

    bool operator < (const sol &A) const {
        return money_per_day < A.money_per_day;
    }

    int64 earned(int day) {
        int64 x = day - start;
        return money_per_day * x + prev_money;
    }
};

void max_self(int64 &a, int64 b) {
    a = max(a, b);
}

void solve() {
    int N, C, D;
    cin >> N >> C >> D;
    vector<machine> machines(N);
    for (auto &m : machines)
        m.read();
    sort(machines.begin(), machines.end());
    set<sol> hull;
    int64 best = C;
    for (auto m : machines) {
        for (auto s : hull)
            max_self(best, s.earned(m.day - 1));
        while ((int)hull.size() >= 2) {
            sol l1 = *hull.begin();
            sol l2 = *hull.upper_bound(l1);
            if (l1.earned(m.day - 1) > l2.earned(m.day - 1))
                break;
            hull.erase(hull.begin());
        }
        if (!hull.empty()) {
            sol l = *hull.begin();
            max_self(best, l.earned(m.day - 1));
        }
        if (m.price > best)
            continue;
        int64 prev_best = best - m.price + m.resale;
        sol new_sol(m.day, m.money_per_day, prev_best);
        hull.insert(new_sol);
        /// ...
    }
    for (auto s : hull)
        max_self(best, s.earned(D));
    cout << best << '\n';
}

int main() {
    fastIO();
    solve();
    return 0;
}