考虑 dp，\(f_i\) 设在 \(t_i\) 时刻到达第 \(i\) 个点，能获得的最大收益。
转移：\(f_i = f_j + a_i\)，其中 \(j\) 能转移到 \(i\) 的充要条件有：
- \(t_j \le t_i\)
- \(y_j \le y_i\)
- \(|x_i - x_j| + y_i - y_j \le t_i - t_j\)
第三个条件表示从 \(j\) 走到 \(i\) 时间要足够。
拆第三个条件的绝对值，得：
- \(x_i - x_j + y_i - y_j \le t_i - t_j\)
- \(x_j - x_i + y_i - y_j \le t_i - t_j\)
移项，得：
- \(t_j - x_j - y_j \le t_i - x_i - y_i\)
- \(t_j + x_j - y_j \le t_i + x_i - y_i\)
这样你就得到了四个条件。乍一看好像是四维偏序！但是你发现若满足 \(|x_i - x_j| + y_i - y_j \le t_i - t_j\)，则一定满足 \(t_i - t_j \ge 0\)，因此可以省略一个条件。
接下来跑 cdq 优化 dp 即可。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, f[maxn], lsh[maxn], tot;
struct node {
ll t, x, y, v, z, id, k;
} a[maxn], b[maxn];
bool cmp1(node a, node b) {
if (a.y != b.y) {
return a.y < b.y;
} else if (a.k != b.k) {
return a.k < b.k;
} else {
return a.z < b.z;
}
}
bool cmp2(node a, node b) {
if (a.k != b.k) {
return a.k < b.k;
} else if (a.z != b.z) {
return a.z < b.z;
} else {
return a.y < b.y;
}
}
namespace BIT {
ll c[maxn];
void init() {
for (int i = 0; i < maxn; ++i) {
c[i] = -inf;
}
}
void update(int x, ll d) {
for (int i = x; i < maxn; i += (i & (-i))) {
c[i] = max(c[i], d);
}
}
ll query(int x) {
ll res = -inf;
for (int i = x; i; i -= (i & (-i))) {
res = max(res, c[i]);
}
return res;
}
void clear(int x) {
for (int i = x; i < maxn; i += (i & (-i))) {
c[i] = -inf;
}
}
}
void cdq(int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
cdq(l, mid);
for (int i = l; i <= r; ++i) {
b[i] = a[i];
}
sort(b + l, b + mid + 1, cmp2);
sort(b + mid + 1, b + r + 1, cmp2);
int p1 = l, p2 = mid + 1;
while (p1 <= mid && p2 <= r) {
if (b[p1].k <= b[p2].k) {
BIT::update(b[p1].z, f[b[p1].id]);
++p1;
} else {
f[b[p2].id] = max(f[b[p2].id], BIT::query(b[p2].z) + b[p2].v);
++p2;
}
}
while (p1 <= mid) {
BIT::update(b[p1].z, f[b[p1].id]);
++p1;
}
while (p2 <= r) {
f[b[p2].id] = max(f[b[p2].id], BIT::query(b[p2].z) + b[p2].v);
++p2;
}
for (int i = l; i <= mid; ++i) {
BIT::clear(b[i].z);
}
cdq(mid + 1, r);
}
void solve() {
BIT::init();
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld%lld", &a[i].t, &a[i].x, &a[i].y, &a[i].v);
lsh[++tot] = a[i].t + a[i].x - a[i].y;
a[i].k = a[i].t - a[i].x - a[i].y;
a[i].id = i;
}
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
for (int i = 1; i <= n; ++i) {
a[i].z = lower_bound(lsh + 1, lsh + tot + 1, a[i].t + a[i].x - a[i].y) - lsh + 1;
}
a[0].z = 1;
sort(a + 1, a + n + 1, cmp1);
f[0] = 0;
for (int i = 1; i <= n; ++i) {
f[i] = -inf;
}
cdq(0, n);
printf("%lld\n", *max_element(f, f + n + 1));
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}