Pagini recente » Cod sursa (job #567735) | Cod sursa (job #646555) | Cod sursa (job #2856280) | Cod sursa (job #2870591) | Cod sursa (job #1885601)
#include <iostream>
#include <fstream>
#define Nmax 100005
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,m,j;
long long dp[Nmax],val[Nmax],val2[Nmax],maxim;
pair<int,int>p[Nmax];
bool cmp(pair<int,int>a,pair<int,int>b)
{
return(a.second<b.second);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>p[i].first>>p[i].second;
sort(p+1,p+n+1,cmp);
m=p[n].second;
for(int i=1;i<=m;i++)
{
dp[i]=dp[i-1];
for(int j=1;j<=n;j++)
if(i==p[j].second)
dp[i]=max(dp[i],dp[p[j].first]+p[j].second-p[j].first);
}
fout<<dp[m];
/*for(int i=1;i<=n;i++)if(p[i].second!=p[i-1].second)
val[++m]=p[i].second;
for(int i=1;i<=n;i++)
{
while(val[j]<=p[i].first && val[j+1]<=p[i].first)j++;
val2[i]=j;
}
j=1;
for(int i=1;i<=m;i++)
{
while(val[i]==p[j].second && j<=n)
{
dp[i]=max(dp[i],dp[val2[j]]+p[j].second-p[j].first);
j++;
}
maxim=max(maxim,dp[i]);
}
fout<<maxim;*/
return 0;
}