Pagini recente » Cod sursa (job #693350) | Cod sursa (job #1033312) | Cod sursa (job #1675628) | Cod sursa (job #1438170) | Cod sursa (job #2136070)
#include <cstdio>
#include <algorithm>
using namespace std;
int d[100001];
pair <int,int> v[100001];
int main()
{
FILE *fin=fopen ("heavymetal.in","r");
FILE *fout=fopen ("heavymetal.out","w");
int n,i,st,dr,mid,inc;
fscanf (fin,"%d",&n);
for (i=1;i<=n;i++)
fscanf (fin,"%d%d",&v[i].second,&v[i].first);
sort (v+1,v+n+1);
d[1]=v[1].first-v[1].second;
for (i=2;i<=n;i++){
inc=v[i].second; // caut cel mai mare sfarsit mai mic decat inceputul actual
st=1;
dr=i-1;
while (st<=dr){
mid=(st+dr)/2;
if (v[mid].first<=inc)
st=mid+1;
else dr=mid-1;
}
d[i]=max(v[i].first-v[i].second+d[dr],d[i-1]);
}
fprintf (fout,"%d",d[n]);
return 0;
}