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