Guest User

Untitled

a guest
Jul 16th, 2019
284
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.95 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // projects
  4. //
  5. // Created by r on 6/29/19.
  6. // Copyright © 2019 r. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <algorithm>
  11. #include <cstring>
  12. #include <iomanip>
  13. #include <fstream>
  14. #include <cmath>
  15. #include <vector>
  16. #include <set>
  17. #include <unordered_set>
  18. #include <unordered_map>
  19. #include <map>
  20. #include <stack>
  21. #include <queue>
  22. #include <assert.h>
  23. #include <limits>
  24. #include <cstdio>
  25. using namespace std;
  26.  
  27. //#define RDEBUG 1
  28. #ifdef RDEBUG
  29. #define D(x) x
  30. #else
  31. #define D(x)
  32. #endif
  33. #define inf 0x7fffffff
  34. #define MOD 1000000007
  35.  
  36. typedef long long ll;
  37.  
  38.  
  39. ll add(ll a, ll b) {
  40. a += b;
  41. if(a >= MOD) {
  42. a -= MOD;
  43. }
  44. return a;
  45. }
  46. ll sub(ll a, ll b) {
  47. a -= b;
  48. if(a < 0) {
  49. a += MOD;
  50. }
  51. return a;
  52. }
  53.  
  54. ll mul(ll a, ll b) {
  55. return (a * b)%MOD;
  56. }
  57.  
  58. void add_self(ll& a, ll b) {
  59. a = add(a, b);
  60. }
  61. void sub_self(ll& a, ll b) {
  62. a = sub(a, b);
  63. }
  64. void mul_self(ll& a, ll b) {
  65. a = mul(a, b);
  66. }
  67.  
  68.  
  69. const ll MAXN = 200010;
  70.  
  71. ll N;
  72.  
  73. pair<pair<ll, ll>, ll> intervals[MAXN];
  74. ll dp[MAXN];
  75.  
  76. bool cmp(pair<pair<ll, ll>, ll> a, pair<pair<ll, ll>, ll> b) {return a.first<b.first;}
  77.  
  78. ll binsearch(ll l, ll r, ll target) {
  79. while (l<r) {
  80. ll mid = l+(r-l)/2;
  81. if (intervals[mid].first.first<target) {
  82. l = mid+1;
  83. } else {
  84. r = mid;
  85. }
  86. }
  87. return l;
  88. }
  89.  
  90.  
  91. int main() {
  92. ios_base :: sync_with_stdio(false);
  93. cin.tie(nullptr);
  94. cin >> N;
  95. for (ll i = 0; i<N; i++) {
  96. cin >> intervals[i].first.first >> intervals[i].first.second >> intervals[i].second;
  97. }
  98. sort(intervals, intervals+N, cmp);
  99. intervals[N] = {{1e10, 1e10}, 0};
  100. dp[N] = 0;
  101. for (ll i = N-1; i>=0; i--) {
  102. ll ind = binsearch(i, N, intervals[i].first.second+1);
  103. dp[i] = max(dp[i+1], dp[ind]+intervals[i].second);
  104. }
  105. cout << dp[0] << endl;
  106. return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment