#include #include using namespace std; using int64 = long long; // const int mod = 1e9 + 7; const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in: v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e: t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } /** * @brief Segment Tree(セグメント木) * @docs docs/segment-tree.md */ template< typename Monoid, typename F > struct SegmentTree { int n, sz; vector< Monoid > seg; const F f; const Monoid M1; SegmentTree() = default; explicit SegmentTree(int n, const F f, const Monoid &M1) : n(n), f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } explicit SegmentTree(const vector< Monoid > &v, const F f, const Monoid &M1) : SegmentTree((int) v.size(), f, M1) { build(v); } void build(const vector< Monoid > &v) { assert(n == (int) v.size()); for(int k = 0; k < n; k++) seg[k + sz] = v[k]; for(int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void set(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid get(int k) const { return seg[k + sz]; } Monoid operator[](const int &k) const { return get(k); } void apply(int k, const Monoid &x) { k += sz; seg[k] = f(seg[k], x); while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid prod(int l, int r) const { Monoid L = M1, R = M1; for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) { if(l & 1) L = f(L, seg[l++]); if(r & 1) R = f(seg[--r], R); } return f(L, R); } Monoid all_prod() const { return seg[1]; } template< typename C > int find_first(int l, const C &check) const { if(l >= n) return n; l += sz; Monoid sum = M1; do { while((l & 1) == 0) l >>= 1; if(check(f(sum, seg[l]))) { while(l < sz) { l <<= 1; auto nxt = f(sum, seg[l]); if(not check(nxt)) { sum = nxt; l++; } } return l + 1 - sz; } sum = f(sum, seg[l++]); } while((l & -l) != l); return n; } template< typename C > int find_last(int r, const C &check) const { if(r <= 0) return -1; r += sz; Monoid sum = 0; do { r--; while(r > 1 and (r & 1)) r >>= 1; if(check(f(seg[r], sum))) { while(r < sz) { r = (r << 1) + 1; auto nxt = f(seg[r], sum); if(not check(nxt)) { sum = nxt; r--; } } return r - sz; } sum = f(seg[r], sum); } while((r & -r) != r); return -1; } }; template< typename Monoid, typename F > SegmentTree< Monoid, F > get_segment_tree(int N, const F &f, const Monoid &M1) { return SegmentTree{N, f, M1}; } template< typename Monoid, typename F > SegmentTree< Monoid, F > get_segment_tree(const vector< Monoid > &v, const F &f, const Monoid &M1) { return SegmentTree{v, f, M1}; } template< typename structure_t, typename get_t, typename update_t, typename merge_f, typename range_get_f, typename update_f > struct SegmentTree2DCompressed { int sz; vector< structure_t > seg; const merge_f f; const range_get_f g; const update_f h; const get_t identity; vector< vector< int > > LL, RR; vector< vector< int > > beet; SegmentTree2DCompressed(int n, const merge_f &f, const range_get_f &g, const update_f &h, const get_t &identity) : f(f), g(g), h(h), identity(identity) { sz = 1; while(sz < n) sz <<= 1; beet.resize(2 * sz); LL.resize(2 * sz); RR.resize(2 * sz); } void update(int a, int x, update_t z, int k, int l, int r) { if(r <= a || a + 1 <= l) return; if(a <= l && r <= a + 1) return h(seg[k], x, z); update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1); update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r); return h(seg[k], x, z); } void update(int x, int y, update_t z) { y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]); return update(x, y, z, 1, 0, sz); } get_t query(int a, int b, int x, int y, int k, int l, int r) { if(a >= r || b <= l) return identity; if(a <= l && r <= b) return g(seg[k], x, y); return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1), query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r)); } get_t query(int a, int b, int x, int y) { x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]); y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]); return query(a, b, x, y, 1, 0, sz); } void build() { for(int k = (int) beet.size() - 1; k >= sz; k--) { sort(begin(beet[k]), end(beet[k])); beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); } for(int k = sz - 1; k > 0; k--) { beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size()); merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]), begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k])); beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); LL[k].resize(beet[k].size() + 1); RR[k].resize(beet[k].size() + 1); int tail1 = 0, tail2 = 0; for(int i = 0; i < beet[k].size(); i++) { while(tail1 < beet[2 * k + 0].size() && beet[2 * k + 0][tail1] < beet[k][i]) ++tail1; while(tail2 < beet[2 * k + 1].size() && beet[2 * k + 1][tail2] < beet[k][i]) ++tail2; LL[k][i] = tail1, RR[k][i] = tail2; } LL[k][beet[k].size()] = (int) beet[2 * k + 0].size(); RR[k][beet[k].size()] = (int) beet[2 * k + 1].size(); } for(int k = 0; k < beet.size(); k++) { structure_t vs((int) beet[k].size(), f, -infll); seg.emplace_back(vs); } } void preupdate(int x, int y) { beet[x + sz].push_back(y); } }; int main() { int N; cin >> N; vector< tuple< int, int, int > > ds; ds.reserve(N + 1); for(int i = 0; i < N; i++) { int t, x, v; cin >> t >> x >> v; ds.emplace_back(t, x, v); } ds.emplace_back(0, 0, 0); sort(begin(ds), end(ds)); vector< int64 > dp(ds.size(), -infll); dp[0] = 0; vector< int > l, r, m; l.reserve(N + 1); r.reserve(N + 1); m.reserve(N + 1); for(auto&[t, x, v]: ds) { l.emplace_back(t + x); r.emplace_back(t - x); m.emplace_back(x); } sort(begin(l), end(l)); l.erase(unique(begin(l), end(l)), end(l)); sort(begin(r), end(r)); r.erase(unique(begin(r), end(r)), end(r)); sort(begin(m), end(m)); m.erase(unique(begin(m), end(m)), end(m)); vector< int > ldx(ds.size()), rdx(ds.size()), mdx(ds.size()); for(int i = 0; i < (int) ds.size(); i++) { auto[t, x, v]=ds[i]; ldx[i] = lower_bound(begin(l), end(l), t + x) - begin(l); rdx[i] = lower_bound(begin(r), end(r), t - x) - begin(r); mdx[i] = lower_bound(begin(m), end(m), x) - begin(m); } auto f = [](int64 a, int64 b) { return max(a, b); }; // みんなの2D segment tree using BIT = SegmentTree< int64, decltype(f) >; auto g = [](BIT &k, int x, int y) { return k.prod(x, y); }; auto h = [](BIT &k, int x, int64 y) { k.apply(x, y); }; SegmentTree2DCompressed< BIT, int64, int64, decltype(f), decltype(g), decltype(h) > lseg(m.size(), f, g, h, -infll); SegmentTree2DCompressed< BIT, int64, int64, decltype(f), decltype(g), decltype(h) > rseg(m.size(), f, g, h, -infll); for(int i = 0; i < (int) ds.size(); i++) { lseg.preupdate(mdx[i], ldx[i]); rseg.preupdate(mdx[i], rdx[i]); } lseg.build(); rseg.build(); lseg.update(mdx[0], ldx[0], 0); rseg.update(mdx[0], rdx[0], 0); int64 ret = 0; for(int i = 1; i < (int) ds.size(); i++) { auto[t2, x2, v2] = ds[i]; auto v = max(lseg.query(mdx[i], m.size(), 0, ldx[i] + 1), rseg.query(0, mdx[i], 0, rdx[i] + 1)); v += v2; chmax(ret, v); lseg.update(mdx[i], ldx[i], v); rseg.update(mdx[i], rdx[i], v); } cout << ret << "\n"; }