Submission #2472815

---

Source Code Expand

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

typedef long long ll;
const int N = 4005;
const ll INF = 1e18;

int n, T;
ll dp[N][N];

struct ConvexHullTrick {
	struct line {
		ll a; ll b;
		line(ll a = 0, ll b = 0) : a(a), b(b) {}
	};

	bool bad(line l1, line l2, line l3) {
		// intersection(l1, l3) < intersection(l1, l2)
		return 1LL * (l1.b - l3.b) * (l2.a - l1.a) < 1LL * (l3.a - l1.a) * (l1.b - l2.b);
	}

	vector <line> L;
	void add(line d) {
		// d is added according to the increasing order of f[]
		if (!L.empty() && L.back().a == d.a) {
			if (L.back().b < d.b) return; // d is not optimal
			else L.pop_back(); // L.back() is not optimal anymore
		}
		while(L.size() >= 2 && bad(L[(int) L.size() - 2], L[(int) L.size() - 1], d)) {
			L.pop_back();
		}
		L.push_back(d);
	}

	ll get(ll x) { // x is increasing
		if (L.empty()) return INF;
		while(L.size() >= 2 && 1LL * L[0].a * x + L[0].b >= 1LL * L[1].a * x + L[1].b) {
			L.erase(L.begin());
		}
		return 1LL * L[0].a * x + L[0].b;
	}
} cvh[N];

struct song {
	int t; int p; int f;
	inline bool operator < (const song &other) const {
		return f < other.f;
	}
} a[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> T;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].t >> a[i].p >> a[i].f;
	}
	sort(a + 1, a + n + 1);

	for (int i = 1; i <= n; ++i) {
		for (int t = 0; t <= T; ++t) {
			dp[i][t] = -INF;
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int t = a[i].t; t <= T; ++t) {
			if (t == a[i].t) {
				dp[i][t] = a[i].p;
				continue;
			}

			ll g = cvh[t - a[i].t].get(2LL * a[i].f);
			if (g == INF) continue;
			
			dp[i][t] = -g + a[i].p - 1LL * a[i].f * a[i].f;
			//cerr << i << ' ' << t << ' ' << dp[i][t] << endl;
		}

		for (int t = a[i].t; t <= T; ++t) {
			if (dp[i][t] != -INF) {
				cvh[t].add({(ll)-a[i].f, 1LL * a[i].f * a[i].f - dp[i][t]});
			}
		}
	}

	ll res = -INF;
	for (int t = 1; t <= T; ++t) {
		for (int i = 1; i <= n; ++i) {
			res = max(res, dp[i][t]);
		}
	}

	printf("%lld\n", res);
}

Submission Info

Judge Result