Cod sursa(job #586712)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 2 mai 2011 20:12:14
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
using namespace std;
int n,x,y,i,j,p,k,maxc;
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;
  for (j=i;j>=1;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;
}

/*#include <iostream>
#include <fstream>
using namespace std;
int n,x,y,i,j,p,k,maxc;
int a[100000],b[100000],c[100000];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int main()
{
 f>>n;
 for(i=1;i<=n;i++)
 f>>a[i]>>b[i];

 for (i=1;i<=n;i++)
 for (j=i+1;j<=n;j++)
  {
   if (a[i]>a[j]) {swap(a[i],a[j]);swap(b[i],b[j]);}
   if (a[i]==a[j])
   if (b[i]>b[j]) swap (b[i],b[j]);
  }
  c[1]=b[1]-a[1];


  for (i=2;i<=n;i++)
  {
      maxc=0;
  for (j=i;j>=1;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;
}
*/