Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // projects
- //
- // Created by r on 6/29/19.
- // Copyright © 2019 r. All rights reserved.
- //
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <iomanip>
- #include <fstream>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <unordered_set>
- #include <unordered_map>
- #include <map>
- #include <stack>
- #include <queue>
- #include <assert.h>
- #include <limits>
- #include <cstdio>
- using namespace std;
- //#define RDEBUG 1
- #ifdef RDEBUG
- #define D(x) x
- #else
- #define D(x)
- #endif
- #define inf 0x7fffffff
- #define MOD 1000000007
- typedef long long ll;
- ll add(ll a, ll b) {
- a += b;
- if(a >= MOD) {
- a -= MOD;
- }
- return a;
- }
- ll sub(ll a, ll b) {
- a -= b;
- if(a < 0) {
- a += MOD;
- }
- return a;
- }
- ll mul(ll a, ll b) {
- return (a * b)%MOD;
- }
- void add_self(ll& a, ll b) {
- a = add(a, b);
- }
- void sub_self(ll& a, ll b) {
- a = sub(a, b);
- }
- void mul_self(ll& a, ll b) {
- a = mul(a, b);
- }
- const ll MAXN = 200010;
- ll N;
- pair<pair<ll, ll>, ll> intervals[MAXN];
- ll dp[MAXN];
- bool cmp(pair<pair<ll, ll>, ll> a, pair<pair<ll, ll>, ll> b) {return a.first<b.first;}
- ll binsearch(ll l, ll r, ll target) {
- while (l<r) {
- ll mid = l+(r-l)/2;
- if (intervals[mid].first.first<target) {
- l = mid+1;
- } else {
- r = mid;
- }
- }
- return l;
- }
- int main() {
- ios_base :: sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> N;
- for (ll i = 0; i<N; i++) {
- cin >> intervals[i].first.first >> intervals[i].first.second >> intervals[i].second;
- }
- sort(intervals, intervals+N, cmp);
- intervals[N] = {{1e10, 1e10}, 0};
- dp[N] = 0;
- for (ll i = N-1; i>=0; i--) {
- ll ind = binsearch(i, N, intervals[i].first.second+1);
- dp[i] = max(dp[i+1], dp[ind]+intervals[i].second);
- }
- cout << dp[0] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment