Cod sursa(job #1851796)

Utilizator dinurosca03Rosca Dinu Cristian dinurosca03 Data 20 ianuarie 2017 09:01:36
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct eu{int x,y,val;};
eu v[100001];
int i,j,n,m,x,k;
bool sorting(eu a,eu b)
    {
    return a.y<b.y;
    }
int main ()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
    scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,sorting);
for(i=1;i<=n;i++)
    {
    int l1=1,l2=i-1,o=0;
    while(l1<=l2)
        {
        int mid=(l1+l2)/2;
        if(v[mid].y<=v[i].x)
            {
            o=mid;
            l1=mid+1;
            }
        else
            l2=mid-1;
        }
    v[i].val=max(v[i-1].val,v[i].y-v[i].x+v[o].val);
    }
printf("%d\n",v[n].val);
return 0;
}