Cod sursa(job #1197691)

Utilizator azkabancont-vechi azkaban Data 13 iunie 2014 13:48:20
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");

void sort(long left, long right, long A[],long B[])
{
  long i,j,pivot;
  i=left; j=right; pivot=B[(right+left)/2];
   do {
                 while (B[i]<pivot) ++i;
                 while (B[j]>pivot) --j;
                 if (i<=j ) {
                              swap(A[i],A[j]);
                              swap(B[i],B[j]);
                              ++i;
                              --j;
                             }
               }
   while (i<=j);
   if (i<right) sort(i,right,A,B);
   if (j>left) sort(left,j,A,B);  
}

long n,maxim,maxim2,A[100000],B[100000],S[100000];
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i) cin>>A[i]>>B[i];
    sort(1,n,A,B);
    for (int i=1;i<=n;++i) S[i]=B[i]-A[i];
    for (int i=2;i<=n;++i){
                          maxim2=0;
                          for (int j=1;j<i;++j) 
                                               if (B[j]<=A[i] && A[j]<=A[i]) maxim2=max(maxim2,S[j]);
                                               S[i]+=maxim2;
                           }
    maxim=0;
    for (int i=1;i<=n;i++) maxim=max(maxim,S[i]);
    cout<<maxim<<"\n";
    return 0;
}