Pagini recente » Cod sursa (job #1130499) | Cod sursa (job #857906) | Cod sursa (job #983947) | Cod sursa (job #129001) | Cod sursa (job #649909)
Cod sursa(job #649909)
#include <iostream>
#include <fstream>
using namespace std;
int n,x,y,i,j,p,k,maxc,okz;
int a[100000],b[100000],c[100000];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
void poz(int li,int ls,int&k)
{
int i=li,j=ls,c,i1=0,j1=-1;
while(i<j)
{
if(a[i]>a[j]||(a[i]==a[j]&&b[i]>b[j]))
{
swap (a[i],a[j]);swap (b[i],b[j]);
c=i1; i1=-j1; j1=-c;
}
i=i+i1; j=j+j1;
}
k=i;
}
void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls,k); quick(li,k-1); quick(k+1,ls);
}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>a[i]>>b[i];
quick (1,n);
c[1]=b[1]-a[1];
for (i=2;i<=n;i++)
{
maxc=0;
if (i>4000) okz=i-4000 ;else okz=1;
for (j=i;j>=okz;j--)
if (a[i]>=b[j]&&c[j]>maxc)
{maxc=c[j];}
c[i]=c[i]+maxc+b[i]-a[i];
}
maxc=0;
for (i=1;i<=n;i++)
if (c[i]>maxc) maxc=c[i];
g<<maxc;
f.close();
g.close();
return 0;
}