Pagini recente » Cod sursa (job #2641719) | Cod sursa (job #653359) | Cod sursa (job #449021) | Cod sursa (job #154027) | Cod sursa (job #2055218)
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#define DX 200050
using namespace std;
fstream fin("heavymetal.in",ios::in),fout("heavymetal.out",ios::out);
map<int,int> mp,pm;
int n,nr,dp[DX],maxi;
struct str
{
int a,b;
bool operator < (str cl) const
{
return (b<(cl.b));
}
};
vector<int> norm;
vector<str> v;
void normalizare()
{
int i,j;
sort(norm.begin(),norm.end());
for(i=0;i<norm.size();i++)
{
nr++;
mp[norm[i]]=nr;
pm[nr]=norm[i];
for(j=i;((j<norm.size()) && (norm[i]==norm[j]));j++);
i=j-1;
}
}
void solv()
{
int i,j=0,a,b,c;
for(i=2;i<=nr;i++)
{
dp[i]=dp[i-1];
while(j<v.size() && v[j].b<=pm[i])
{
a=mp[v[j].a]; b=mp[v[j].b]; c=v[j].b-v[j].a;
dp[i]=max(dp[i],dp[a]+c);
j++;
}
maxi=max(maxi,dp[i]);
}
}
int main()
{
int i,j,a,b;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a>>b;
v.push_back({a,b});
norm.push_back(a); norm.push_back(b);
}
normalizare();
sort(v.begin(),v.end());
solv();
fout<<maxi;
}