Cod sursa(job #586709)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 2 mai 2011 20:03:37
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 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");
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;
}