Cod sursa(job #927961)

Utilizator a.raduAndrei Radu a.radu Data 26 martie 2013 10:07:47
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
using namespace std;
long long a[100001],b[100001],c[100001],n,i,max,y,maxi;
void qsort(long l,long r)
{
long ii,jj,x,y;
ii=l;jj=r;x=a[(l+r)/2];
do{
while(a[ii]<x){ii++;}
while(a[jj]>x){jj--;}
if(ii<=jj){
        {
        y=a[ii];a[ii]=a[jj];a[jj]=y;
        y=b[ii];b[ii]=b[jj];b[jj]=y;
        }
ii++;jj--;
        }
  }while(ii<=jj);
  if(l<jj){qsort(l,jj);}
  if(ii<r){qsort(ii,r);}
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%lld",&n);
for (i=1; i<=n; i++)
    scanf("%lld%lld",&a[i],&b[i]);

qsort(1,n);
b[0]=0;
c[0]=0;
c[1]=b[1]-a[1];
for (i=2; i<=n; i++)
    {
    max=0;
    for (y=0; y<i; y++)
       if (b[y]<=a[i])
            {
            if (max<c[y]+b[i]-a[i])
                    max=c[y]+b[i]-a[i];
            }
    c[i]=max;
    if (maxi<max)
        maxi=max;
    }
printf("%lld",maxi);
return 0;
}