## 题解

$$f[i]=max(f[j]) \quad(j \lt i \; \&\& \;|p[i]-p[j]|\leq 2(t[i]-t[j]))$$

$$p[i]-p[j]\leq 2(t[i] – t[j]) \; \& \& \; p[j]-p[i]\leq 2(t[i]-t[j])$$

$$2t[j]-p[j]\leq 2t[i] – p[i] \; \& \& \; 2t[j]+p[j]\leq 2t[i]+p[i]$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
struct node{
int x, y, v, id;
friend bool operator < (node x, node y)
{
return x.x < y.x;
}
}a[N];
int t, p, v, cnt, u[N], f[N], ans, n, m;
inline bool cmp (node x, node y) {return x.y < y.y;}
namespace BIT{
int c[N];
inline void add (int x, int val) {for (int i = x; i <= cnt; i += lowbit(i)) c[i] = std::max(c[i], val);}
inline int query (int x) {int ret = 0; for (int i = x; i; i -= lowbit(i)) ret = std::max(c[i], ret); return ret;}
};
int main ()
{
scanf("%d %d", &m, &n);
fo (i, 1, n)
{
scanf("%d %d %d", &t, &p, &v);
a[i].x = 2 * t - p;
a[i].y = 2 * t + p;
a[i].v = v;
a[i].id = i;
}
std::sort(a + 1, a + n + 1, cmp);
cnt = 1; u[1] = 1;
fo (i, 2, n)
{
if (a[i].y != a[i - 1].y)
++cnt;
u[i] = cnt;
}
fo (i, 1, n)
a[i].y = u[i];
std::sort(a + 1, a + n + 1);
fo (i, 1, n)
{
f[i] = BIT::query(a[i].y) + a[i].v;
ans = std::max(ans, f[i]);
}
printf("%d", ans);
}


### 2 条评论

% QHY Dalao

emmmmm…

#### quhengyi11 · 2018年11月5日 7:36 上午

那啥，这两个花括号我会打呀，你是指 max 那里我用了小括号？好细心 QAQ 我只是可能习惯了打 max 函数所以写成小括号了（还有我喜欢 BIT 压行 QAQ）