Cod sursa(job #1542897)

Utilizator marcdariaDaria Marc marcdaria Data 5 decembrie 2015 19:36:27
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
#define maxi 1000000

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int main()
{
    int N,a[maxi],b[maxi],best[maxi],i,tmax,sol;
    fin>>N;
    for(i=1;i<=N;++i)
       fin>>a[i]>>b[i];
    sort(a+1,a+N+1);
    best[1]=b[1]-a[1];
    sol=best[1];

    for(i=2;i<=N;++i)
    {
        best[i]=best[i-1];
        int s=1;
        int d=i-1;
        int m=0;
        while(s<=d)
        {
            int mij=(s+d)/2;
            if(b[mij]<=a[mij])
            {
                m=mij;
                s=mij+1;
            }
            else
                d=mij-1;
        }
        best[i]=max(best[i],best[m]+b[i]-a[i]);
        sol=max(sol,best[i]);
        }

    fout<<sol;

    return 0;
}