Cod sursa(job #186139)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 26 aprilie 2008 19:44:18
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
// HeavyMetal Infoarena
#include <algorithm>
#include <fstream>
using namespace std;
#define NMAX 10001
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct form
{
    int st;
    int sf;
    unsigned long long solz;
};

int sortare(form a,form b)
{
    return !(a.sf>b.sf||(a.sf==b.sf&&a.sf>b.sf));
}

int main()
{
    int n,i,c=0;
    form A[NMAX];
    unsigned long long sol=0;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>A[i].st>>A[i].sf;
    sort (A+1,A+n+1,sortare);
    A[0].st=A[0].sf=0;
    A[0].solz=0;
    int st,sf,m,sola;
    for (i=1;i<=n;i++)
    {
        sf=i;
        st=0;
        while (st<=sf)
        {
            m=(st+sf)/2;
            if (A[m].sf<=A[i].st)
            {
                sola=m;
                st=m+1;
            }
            else
                sf=m-1;
        }
        A[i].solz=A[sola].solz+A[i].sf-A[i].st;
        if (A[i].solz>sol) sol=A[i].solz;
    }

    fout<<sol;
    fout.close();
    return 0;
}