Cod sursa(job #1722891)

Utilizator plecinspaniaCapsunar plecinspania Data 29 iunie 2016 12:01:01
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct coord
{
    int st,dr;
};

inline bool cmp(const coord A,const coord B)
{
    if(A.dr==B.dr) return A.st<B.st;
    return A.dr<B.dr;
}

coord v[Nmax];
int n,dp[Nmax];

void Citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].st>>v[i].dr;
    fin.close();
    sort(v+1,v+n+1,cmp);
}

inline int Cautbin(int p1,int p2,int val)
{
    int st=p1,dr=p2,mij,sol;
    sol=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij].dr<=val) sol=mij,st=mij+1;
        else dr=mij-1;
    }
    return sol;
}

void Rezolvare()
{
    int i,poz;
    for(i=1;i<=n;i++)
    {
        poz=Cautbin(1,i-1,v[i].st);
        dp[i]=max(dp[i-1],v[i].dr-v[i].st+dp[poz]);
    }
    fout<<dp[n]<<"\n";
    fout.close();
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}