Pagini recente » Cod sursa (job #360802) | Cod sursa (job #3291099) | Cod sursa (job #226682) | Cod sursa (job #1886922) | Cod sursa (job #2575586)
#include <bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n,i,dp[100000],mx;
struct metal
{
int start;
int sf;
} v[100];
bool comp(metal a,metal b)
{
return a.start<b.start;
}
int caut(int poz)
{
int st=1;
int dr=poz;
int mx=0;
while(st<=dr)
{
int mid=(st+dr)/2;
if(dp[mid]!=0)
{
mx=max(mx,dp[mid]);
st=mid+1;
}
else dr=mid-1;
}
return mx;
}
int main()
{
f>>n;
for(i=1; i<=n; i++)
f>>v[i].start>>v[i].sf;
sort(v+1,v+n+1,comp);
for(i=1; i<=n; i++)
{
if(dp[v[i].start]==0 and i!=1)
{
dp[v[i].start]=caut(v[i].start);
}
dp[v[i].sf]=max(dp[v[i].sf],dp[v[i].start]+v[i].sf-v[i].start);
mx=max(mx,dp[v[i].sf]);
}g<<mx;
}