Cod sursa(job #2136070)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 19 februarie 2018 16:53:32
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <algorithm>

using namespace std;
int d[100001];
pair <int,int> v[100001];
int main()
{
    FILE *fin=fopen ("heavymetal.in","r");
    FILE *fout=fopen ("heavymetal.out","w");
    int n,i,st,dr,mid,inc;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&v[i].second,&v[i].first);
    sort (v+1,v+n+1);
    d[1]=v[1].first-v[1].second;
    for (i=2;i<=n;i++){
        inc=v[i].second; // caut cel mai mare sfarsit mai mic decat inceputul actual
        st=1;
        dr=i-1;
        while (st<=dr){
            mid=(st+dr)/2;
            if (v[mid].first<=inc)
                st=mid+1;
            else dr=mid-1;
        }
        d[i]=max(v[i].first-v[i].second+d[dr],d[i-1]);
    }
    fprintf (fout,"%d",d[n]);
    return 0;
}