fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int, int> ii;
  6.  
  7. const int INF = 1e9;
  8. const ll LINF = 1e18;
  9.  
  10. const int N = 2e5 + 5;
  11.  
  12. template<typename T>
  13. void maximize(T& a, const T& b) {
  14. if (b < a) return;
  15. a = b;
  16. }
  17.  
  18. struct project {
  19. int l, r; ll w;
  20. bool operator<(const project& other) const {
  21. return (r < other.r);
  22. }
  23. };
  24.  
  25. int n;
  26. project a[N];
  27.  
  28. ll dp[N]; // dp[i] = Lợi nhuận lớn nhất đạt được khi xét i dự án đầu tiên
  29.  
  30. // Tìm vị trí i lớn nhất sao cho a[i].r < x
  31. int binSearch(int l, int r, int x) {
  32. int ans = -1;
  33. while (l <= r) {
  34. int mid = (l + r) >> 1;
  35. if (a[mid].r < x) {
  36. ans = mid;
  37. l = mid + 1;
  38. }
  39. else {
  40. r = mid - 1;
  41. }
  42. }
  43. return ans;
  44. }
  45.  
  46. int main() {
  47. ios::sync_with_stdio(0); cin.tie(0);
  48. cin >> n;
  49. for (int i = 1; i <= n; i++) {
  50. cin >> a[i].l >> a[i].r >> a[i].w;
  51. }
  52.  
  53. // sort tăng dần theo thời điểm kết thúc của các dự án
  54. sort(a + 1, a + n + 1);
  55.  
  56. for (int i = 1; i <= n; i++) {
  57. // không chọn dự án thứ i
  58. dp[i] = dp[i - 1];
  59. // chỉ chọn dự án thứ i
  60. maximize(dp[i], a[i].w);
  61. // chọn dự án thứ i cùng với một số dự án khác ở trước
  62. int prev_i = binSearch(1, i - 1, a[i].l);
  63. if (prev_i != -1) maximize(dp[i], dp[prev_i] + a[i].w);
  64. }
  65.  
  66. cout << dp[n] << '\n';
  67. }
Success #stdin #stdout 0.01s 5716KB
stdin
4
2 4 4
3 6 6
6 8 2
5 7 3
stdout
7