Problem: Example

Input

2 10
10 200 1
10 100 100


Output

200

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class convex_hull_trick {
    using T = long long;

    bool check(int f1, int f2, T aa, T bb) {
        return (a[f2] - a[f1]) * (bb - b[f2]) >= (b[f2] - b[f1]) * (aa - a[f2]);
    }
    bool check(int f1, int f2, int f3) {
        return (a[f2] - a[f1]) * (b[f3] - b[f2]) >= (b[f2] - b[f1]) * (a[f3] - a[f2]);
    }

    T f(int idx, T x) {
        return a[idx] * x + b[idx];
    }

public:
    convex_hull_trick() = default;
    // a : sorted sequence
    convex_hull_trick(std::vector<T> const& a_, std::vector<T> const& b_) {
        assert(a_.size() == b_.size());
        for(int i = 0; i < a_.size(); ++i) {
            add_f(a_[i], b_[i]);
        }
    }

    void add_f(T aa, T bb) {
        while(a.size() >= 2 && check(a.size() - 2, a.size() - 1, aa, bb)) {
            a.pop_back();
            b.pop_back();
        }
        a.push_back(aa);
        b.push_back(bb);
    }
    T min(T x) {
        assert(a.size() > 0);
        while(a.size() >= 2 && f(0, x) >= f(1, x)) {
            a.pop_front();
            b.pop_front();
        }
        return a[0] * x + b[0];
    }

    bool empty() const {
        return a.size() == 0;
    }

private:
    std::deque<T> a, b; // functions
};

int main() {
    int N, T;
    cin >> N >> T;
    // (f, t, p)
    vector<tuple<ll, ll, ll>> songs;
    for(int i = 0; i < N; ++i) {
        ll t, p, f;
        cin >> t >> p >> f;
        if(t > T) {
            continue;
        }
        songs.emplace_back(f, t, p);
    }
    N = songs.size();
    sort(songs.begin(), songs.end());

    vector<vector<ll>> dp(N + 1, vector<ll>(T + 1));
    vector<convex_hull_trick> cht(T + 1);
    ll res = 0;
    for(int i = 0; i < N; ++i) {
        ll fi, ti, pi;
        tie(fi, ti, pi) = songs[i];
        for(int j = T; j >= ti; --j) {
            if(cht[j - ti].empty()) {
                continue;
            }
            dp[i][j] = -cht[j - ti].min(fi) - fi * fi + pi;
            res = max(res, dp[i][j]);
            cht[j].add_f(-2 * fi, -dp[i][j] + fi * fi);
        }
        dp[i][ti] = max(dp[i][ti], pi);
        res = max(res, dp[i][ti]);
        cht[ti].add_f(-2 * fi, -dp[i][ti] + fi * fi);
    }
    cout << res << endl;
}