#include #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef pair pll; // データ構造 BIT struct BIT { vector data; BIT(int n) : data(n + 1) {} // update(i, v): A[i] = max(A[i], v); void update(int i, ll v) { for(int x = i; x < data.size(); x += x & -x) { data[x] = max(data[x], v); } } // get(i): return max({A[1], A[2], ..., A[i]}) ll get(int i) { ll ret = 0; for(int x = i; x > 0; x -= x & -x) { ret = max(ret, data[x]); } return ret; } }; // O(N^2), TLE解 int main() { int N; cin >> N; map Cake_; // ケーキの情報 (一時保存用) vector> Cake; // ケーキの情報 (dpで使う時用) for(int i = 0; i < N; i++) { ll a, b, c; cin >> a >> b >> c; // aの昇順、aが同じ時はbの降順にソートしつつ、同じ大きさのケーキはカロリーの高いものだけを残す Cake_[{a, -b}] = max(Cake_[{a, -b}], c); } N = Cake_.size(); // 省いたケーキがある場合もあるのでNを更新 // 簡単にアクセスするために中の要素を順番を保ちつつvectorに移し替える。Bのマイナスはもとに戻す for(auto c : Cake_) Cake.push_back(make_tuple(c.first.first, -c.first.second, c.second)); // 座標圧縮 (zip: B[i]をキーとして、それがB全体の小さい方から数えて何番目かを返す) map zip; for(int i = 0; i < N; i++) zip[get<1>(Cake[i])] = 1; int now = 1; for(auto e : zip) zip[e.first] = now++; // BITを使って高速化した動的計画法 BIT bit(N); vector dp(N); for(int i = 0; i < N; i++) { int t = zip[get<1>(Cake[i])]; dp[i] = get<2>(Cake[i]) + bit.get(t - 1); bit.update(t, dp[i]); } cout << *max_element(all(dp)) << endl; return 0; }