#include #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef pair pll; // 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)); // 動的計画法 vector dp(N); for(int i = 0; i < N; i++) { dp[i] = get<2>(Cake[i]); for(int j = 0; j < i; j++) { if (get<1>(Cake[j]) >= get<1>(Cake[i])) continue; // Bに関する条件をチェック dp[i] = max(dp[i], dp[j] + get<2>(Cake[i])); } } cout << *max_element(all(dp)) << endl; return 0; }