Skip to content

Instantly share code, notes, and snippets.

@koosaga
Created June 12, 2016 18:05
Show Gist options
  • Save koosaga/19ad0f218e9c3940517a684ae15f1b5c to your computer and use it in GitHub Desktop.
Save koosaga/19ad0f218e9c3940517a684ae15f1b5c to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
struct intv{
int s, e, x;
}a[10005];
int n;
vector<int> gph[10005];
int dp1[10005], low[10005];
map<int, int> mp[10005];
int get(int x, int y){
if(mp[x].find(y) != mp[x].end()) return mp[x][y];
int ret = dp1[max(low[x], low[y])];
auto t = upper_bound(gph[x].begin(), gph[x].end(), y);
auto u = upper_bound(gph[y].begin(), gph[y].end(), x);
if(t != gph[x].end()) ret = max(ret, get(x, *t) + a[*t].x - a[y].x);
if(u != gph[y].end()) ret = max(ret, get(*u, y) + a[*u].x - a[x].x);
t = lower_bound(gph[x].begin(), gph[x].end(), low[y]);
u = lower_bound(gph[y].begin(), gph[y].end(), low[x]);
if(t != gph[x].end()) ret = max(ret, get(x, *t) + a[*t].x);
if(u != gph[y].end()) ret = max(ret, get(*u, y) + a[*u].x);
return mp[x][y] = ret;
}
void solve(){
cin >> n;
for(int i=0; i<n; i++){
cin >> a[i].s >> a[i].e >> a[i].x;
}
sort(a, a+n, [&](const intv &a, const intv &b){
return pi(a.s, a.e) < pi(b.s, b.e);
});
for(int i=0; i<n; i++){
low[i] = i+1;
for(int j=i+1; j<n; j++){
if(a[i].e >= a[j].s){
gph[i].push_back(j);
gph[j].push_back(i);
low[i] = j+1;
}
else break;
}
}
for(int i=0; i<n; i++){
sort(gph[i].begin(), gph[i].end());
}
for(int i=n-1; i>=0; i--){
dp1[i] = max(dp1[i+1], dp1[low[i]] + a[i].x);
for(auto &j : gph[i]){
get(i, j);
if(i < j) dp1[i] = max(dp1[i], mp[i][j] + a[i].x + a[j].x);
}
}
cout << dp1[0] << endl;
}
void clear(){
for(int i=0; i<n; i++){
gph[i].clear();
mp[i].clear();
}
memset(dp1, 0, sizeof(dp1));
memset(low, 0, sizeof(low));
}
int main(){
int t;
cin >> t;
while(t--){
solve();
clear();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment