// #pragma comment(linker, "/stack:200000000") #include #include #include namespace suisen { // ! utility template using constraints_t = std::enable_if_t, std::nullptr_t>; template constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) { if constexpr (cond_v) { return std::forward(then); } else { return std::forward(or_else); } } // ! function template using is_same_as_invoke_result = std::is_same, ReturnType>; template using is_uni_op = is_same_as_invoke_result; template using is_bin_op = is_same_as_invoke_result; template using is_comparator = std::is_same, bool>; // ! integral template >> constexpr int bit_num = std::numeric_limits>::digits; template struct is_nbit { static constexpr bool value = bit_num == n; }; template static constexpr bool is_nbit_v = is_nbit::value; // ? template struct safely_multipliable {}; template <> struct safely_multipliable { using type = long long; }; template <> struct safely_multipliable { using type = __int128_t; }; template <> struct safely_multipliable { using type = float; }; template <> struct safely_multipliable { using type = double; }; template <> struct safely_multipliable { using type = long double; }; template using safely_multipliable_t = typename safely_multipliable::type; } // namespace suisen // ! type aliases using i128 = __int128_t; using u128 = __uint128_t; using ll = long long; using uint = unsigned int; using ull = unsigned long long; template using vec = std::vector; template using vec2 = vec>; template using vec3 = vec>; template using vec4 = vec>; template using pq_greater = std::priority_queue, std::greater>; template using umap = std::unordered_map; // ! macros (capital: internal macro) #define OVERLOAD2(_1,_2,name,...) name #define OVERLOAD3(_1,_2,_3,name,...) name #define OVERLOAD4(_1,_2,_3,_4,name,...) name #define REP4(i,l,r,s) for(std::remove_reference_t>i=(l);i<(r);i+=(s)) #define REP3(i,l,r) REP4(i,l,r,1) #define REP2(i,n) REP3(i,0,n) #define REPINF3(i,l,s) for(std::remove_reference_t>i=(l);;i+=(s)) #define REPINF2(i,l) REPINF3(i,l,1) #define REPINF1(i) REPINF2(i,0) #define RREP4(i,l,r,s) for(std::remove_reference_t>i=(l)+fld((r)-(l)-1,s)*(s);i>=(l);i-=(s)) #define RREP3(i,l,r) RREP4(i,l,r,1) #define RREP2(i,n) RREP3(i,0,n) #define rep(...) OVERLOAD4(__VA_ARGS__, REP4 , REP3 , REP2 )(__VA_ARGS__) #define rrep(...) OVERLOAD4(__VA_ARGS__, RREP4 , RREP3 , RREP2 )(__VA_ARGS__) #define repinf(...) OVERLOAD3(__VA_ARGS__, REPINF3, REPINF2, REPINF1)(__VA_ARGS__) #define CAT_I(a, b) a##b #define CAT(a, b) CAT_I(a, b) #define UNIQVAR(tag) CAT(tag, __LINE__) #define loop(n) for (std::remove_reference_t> UNIQVAR(loop_variable) = n; UNIQVAR(loop_variable) --> 0;) #define all(iterable) (iterable).begin(), (iterable).end() #define input(type, ...) type __VA_ARGS__; read(__VA_ARGS__) // ! I/O utilities // pair template std::ostream& operator<<(std::ostream& out, const std::pair &a) { return out << a.first << ' ' << a.second; } // tuple template std::ostream& operator<<(std::ostream& out, const std::tuple &a) { if constexpr (N >= std::tuple_size_v>) { return out; } else { out << std::get(a); if constexpr (N + 1 < std::tuple_size_v>) { out << ' '; } return operator<<(out, a); } } // vector template std::ostream& operator<<(std::ostream& out, const std::vector &a) { for (auto it = a.begin(); it != a.end();) { out << *it; if (++it != a.end()) out << ' '; } return out; } // array template std::ostream& operator<<(std::ostream& out, const std::array &a) { for (auto it = a.begin(); it != a.end();) { out << *it; if (++it != a.end()) out << ' '; } return out; } inline void print() { std::cout << '\n'; } template inline void print(const Head &head, const Tail &...tails) { std::cout << head; if (sizeof...(tails)) std::cout << ' '; print(tails...); } template auto print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") -> decltype(std::cout << *v.begin(), void()) { for (auto it = v.begin(); it != v.end();) { std::cout << *it; if (++it != v.end()) std::cout << sep; } std::cout << end; } // pair template std::istream& operator>>(std::istream& in, std::pair &a) { return in >> a.first >> a.second; } // tuple template std::istream& operator>>(std::istream& in, std::tuple &a) { if constexpr (N >= std::tuple_size_v>) { return in; } else { return operator>>(in >> std::get(a), a); } } // vector template std::istream& operator>>(std::istream& in, std::vector &a) { for (auto it = a.begin(); it != a.end(); ++it) in >> *it; return in; } // array template std::istream& operator>>(std::istream& in, std::array &a) { for (auto it = a.begin(); it != a.end(); ++it) in >> *it; return in; } template void read(Args &...args) { ( std::cin >> ... >> args ); } // ! integral utilities // Returns pow(-1, n) template constexpr inline int pow_m1(T n) { return -(n & 1) | 1; } // Returns pow(-1, n) template <> constexpr inline int pow_m1(bool n) { return -int(n) | 1; } // Returns floor(x / y) template constexpr inline T fld(const T x, const T y) { return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y; } template constexpr inline T cld(const T x, const T y) { return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y; } template > = nullptr> constexpr inline int popcount(const T x) { return __builtin_popcount(x); } template > = nullptr> constexpr inline int popcount(const T x) { return __builtin_popcount(x); } template > = nullptr> constexpr inline int popcount(const T x) { return __builtin_popcountll(x); } template > = nullptr> constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_lz(const T x) { return x ? __builtin_clzll(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_tz(const T x) { return x ? __builtin_ctzll(x) : suisen::bit_num; } template constexpr inline int floor_log2(const T x) { return suisen::bit_num - 1 - count_lz(x); } template constexpr inline int ceil_log2(const T x) { return floor_log2(x) + ((x & -x) != x); } template constexpr inline int kth_bit(const T x, const unsigned int k) { return (x >> k) & 1; } template constexpr inline int parity(const T x) { return popcount(x) & 1; } struct all_subset { struct all_subset_iter { const int s; int t; constexpr all_subset_iter(int s) : s(s), t(s + 1) {} constexpr auto operator*() const { return t; } constexpr auto operator++() {} constexpr auto operator!=(std::nullptr_t) { return t ? (--t &= s, true) : false; } }; int s; constexpr all_subset(int s) : s(s) {} constexpr auto begin() { return all_subset_iter(s); } constexpr auto end() { return nullptr; } }; // ! container template > = nullptr> auto priqueue_comp(const Comparator comparator) { return std::priority_queue, Comparator>(comparator); } template auto isize(const Iterable &iterable) -> decltype(int(iterable.size())) { return iterable.size(); } template > = nullptr> auto generate_vector(int n, Gen generator) { std::vector v(n); for (int i = 0; i < n; ++i) v[i] = generator(i); return v; } template auto generate_range_vector(T l, T r) { return generate_vector(r - l, [l](int i) { return l + i; }); } template auto generate_range_vector(T n) { return generate_range_vector(0, n); } template void sort_unique_erase(std::vector &a) { std::sort(a.begin(), a.end()); a.erase(std::unique(a.begin(), a.end()), a.end()); } template auto foreach_adjacent_values(InputIterator first, InputIterator last, BiConsumer f) -> decltype(f(*first++, *last), void()) { if (first != last) for (auto itr = first, itl = itr++; itr != last; itl = itr++) f(*itl, *itr); } template auto foreach_adjacent_values(Container c, BiConsumer f) -> decltype(c.begin(), c.end(), void()){ foreach_adjacent_values(c.begin(), c.end(), f); } // ! other utilities // x <- min(x, y). returns true iff `x` has chenged. template inline bool chmin(T &x, const T &y) { if (y >= x) return false; x = y; return true; } // x <- max(x, y). returns true iff `x` has chenged. template inline bool chmax(T &x, const T &y) { if (y <= x) return false; x = y; return true; } namespace suisen {} using namespace suisen; using namespace std; struct io_setup { io_setup(int precision = 20) { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(precision); } } io_setup_ {}; // ! code from here #include #include #include namespace suisen { template class CoordinateCompressorBuilder { public: struct Compressor { public: static constexpr int absent = -1; // default constructor Compressor() : _xs(std::vector{}) {} // Construct from strictly sorted vector Compressor(const std::vector &xs) : _xs(xs) { assert(is_strictly_sorted(xs)); } // Return the number of distinct keys. int size() const { return _xs.size(); } // Check if the element is registered. bool has_key(const T &e) const { return std::binary_search(_xs.begin(), _xs.end(), e); } // Compress the element. if not registered, returns `default_value`. (default: Compressor::absent) int comp(const T &e, int default_value = absent) const { const int res = min_geq_index(e); return res != size() and _xs[res] == e ? res : default_value; } // Restore the element from the index. T decomp(const int compressed_index) const { return _xs[compressed_index]; } // Compress the element. Equivalent to call `comp(e)` int operator[](const T &e) const { return comp(e); } // Return the minimum registered value greater than `e`. if not exists, return `default_value`. T min_gt(const T &e, const T &default_value) const { auto it = std::upper_bound(_xs.begin(), _xs.end(), e); return it == _xs.end() ? default_value : *it; } // Return the minimum registered value greater than or equal to `e`. if not exists, return `default_value`. T min_geq(const T &e, const T &default_value) const { auto it = std::lower_bound(_xs.begin(), _xs.end(), e); return it == _xs.end() ? default_value : *it; } // Return the maximum registered value less than `e`. if not exists, return `default_value` T max_lt(const T &e, const T &default_value) const { auto it = std::upper_bound(_xs.rbegin(), _xs.rend(), e); return it == _xs.rend() ? default_value : *it; } // Return the maximum registered value less than or equal to `e`. if not exists, return `default_value` T max_leq(const T &e, const T &default_value) const { auto it = std::lower_bound(_xs.rbegin(), _xs.rend(), e); return it == _xs.rend() ? default_value : *it; } // Return the compressed index of the minimum registered value greater than `e`. if not exists, return `compressor.size()`. int min_gt_index(const T &e) const { return std::upper_bound(_xs.begin(), _xs.end(), e) - _xs.begin(); } // Return the compressed index of the minimum registered value greater than or equal to `e`. if not exists, return `compressor.size()`. int min_geq_index(const T &e) const { return std::lower_bound(_xs.begin(), _xs.end(), e) - _xs.begin(); } // Return the compressed index of the maximum registered value less than `e`. if not exists, return -1. int max_lt_index(const T &e) const { return int(_xs.rend() - std::upper_bound(_xs.rbegin(), _xs.rend(), e)) - 1; } // Return the compressed index of the maximum registered value less than or equal to `e`. if not exists, return -1. int max_leq_index(const T &e) const { return int(_xs.rend() - std::lower_bound(_xs.rbegin(), _xs.rend(), e)) - 1; } private: std::vector _xs; static bool is_strictly_sorted(const std::vector &v) { return std::adjacent_find(v.begin(), v.end(), std::greater_equal()) == v.end(); } }; CoordinateCompressorBuilder() : _xs(std::vector{}) {} explicit CoordinateCompressorBuilder(const std::vector &xs) : _xs(xs) {} explicit CoordinateCompressorBuilder(std::vector &&xs) : _xs(std::move(xs)) {} template > = nullptr> CoordinateCompressorBuilder(const int n, Gen generator) { reserve(n); for (int i = 0; i < n; ++i) push(generator(i)); } // Attempt to preallocate enough memory for specified number of elements. void reserve(int n) { _xs.reserve(n); } // Add data. void push(const T &first) { _xs.push_back(first); } // Add data. void push(T &&first) { _xs.push_back(std::move(first)); } // Add data in the range of [first, last). template auto push(const Iterator &first, const Iterator &last) -> decltype(std::vector{}.push_back(*first), void()) { for (auto it = first; it != last; ++it) _xs.push_back(*it); } // Add all data in the container. Equivalent to `push(iterable.begin(), iterable.end())`. template auto push(const Iterable &iterable) -> decltype(std::vector{}.push_back(*iterable.begin()), void()) { push(iterable.begin(), iterable.end()); } // Add data. template void emplace(Args &&...args) { _xs.emplace_back(std::forward(args)...); } // Build compressor. auto build() { std::sort(_xs.begin(), _xs.end()), _xs.erase(std::unique(_xs.begin(), _xs.end()), _xs.end()); return Compressor {_xs}; } // Build compressor from vector. static auto build(const std::vector &xs) { return CoordinateCompressorBuilder(xs).build(); } // Build compressor from vector. static auto build(std::vector &&xs) { return CoordinateCompressorBuilder(std::move(xs)).build(); } // Build compressor from generator. template > = nullptr> static auto build(const int n, Gen generator) { return CoordinateCompressorBuilder(n, generator).build(); } private: std::vector _xs; }; } // namespace suisen #ifdef _MSC_VER #include #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder namespace atcoder { template struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(std::vector(n, e())) {} explicit segtree(const std::vector& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder constexpr long long inf = numeric_limits::max() / 2; long long op(long long x, long long y) { return max(x, y); } long long e() { return -inf; } int main() { input(int, n); vector> items(n); read(items); items.emplace_back(0, 0, inf); CoordinateCompressorBuilder builder; for (auto &[t, x, v] : items) { long long a = x + t; long long b = x - t; t = a, x = b; builder.push(b); } auto comp = builder.build(); sort(all(items), [&](auto &p1, auto &p2) { auto &[u1, v1, w1] = p1; auto &[u2, v2, w2] = p2; if (u1 != u2) { return u1 < u2; } else { return v1 > v2; } }); const int m = comp.size(); atcoder::segtree seg(m); for (auto &[u, v, w] : items) { int cv = comp[v]; seg.set(cv, max(seg.get(cv), seg.prod(cv, m) + w)); } print(seg.all_prod()); return 0; }