Pagini recente » Cod sursa (job #1137915) | Cod sursa (job #2497483) | Cod sursa (job #1075570) | Cod sursa (job #1028800) | Cod sursa (job #2041848)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct {
int x,y;
}interv[100005];
int dp[200005],n,m,k,v[200005],fr[200005];
vector<int> inv[200005];
map<int,int> mp;
int main()
{
f>>n; m=2*n;
for(int i=1;i<=n;++i)
{
f>>interv[i].x>>interv[i].y;
v[2*i-1]=interv[i].x;
v[2*i]=interv[i].y;
}
sort(v+1,v+m+1);
for(int i=1;i<=m;++i)
{
if(v[i]!=v[i-1])
{
++k;
mp[v[i]]=k;
fr[k]=v[i];
}
}
for(int i=1;i<=n;++i)
{
interv[i].x=mp[interv[i].x];
interv[i].y=mp[interv[i].y];
inv[interv[i].y].push_back(interv[i].x);
}
for(int i=1;i<=m;++i)
{
dp[i]=dp[i-1];
for(int j=0;j<inv[i].size();++j)
{
dp[i]=max(dp[i],dp[inv[i][j]]+fr[i]-fr[inv[i][j]]);
}
}
g<<dp[m];
return 0;
}