Pagini recente » Cod sursa (job #1547133) | Cod sursa (job #1334977) | Cod sursa (job #2833417) | Cod sursa (job #1758991) | Cod sursa (job #1753930)
#include<bits/stdc++.h>
using namespace std;
struct comparator
{
bool operator()(const pair<int,int> &left,const pair<int,int> &right)
{
return left.second < right.second;
}
};
int n,DP[100010],j;
pair<int , int >v[100010];
int main()
{
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
in>>n;
for(int i = 1; i <= n; i++)
in>>v[i].first>>v[i].second;
sort(v+1 , v+n+1 ,comparator());
/*for(int i = 1; i<= n; i++)
cout<<v[i].first<<" "<<v[i].second;*/
j=1;
for(int i = 1 ; i <= v[n].second ; i++)
{
DP[i] = DP [i-1];
while( v[j].second == i )
DP[i] = max(DP[i] , DP[ v[j].first ] + v[j].second - v[j].first ),j++;
}
out<<DP[v[n].second];
return 0;
}