Cod sursa(job #1781565)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 16 octombrie 2016 23:19:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#include <algorithm>
#define lim 100005
using namespace std;
struct interval{int st,dr;};
interval v[lim];
int d[lim];
//d[i]=timpul maxim daca iau primele i intervale sortate crescator dupa capatul dreapta
//d[i]=v[i].dr-v[i].st+d[j] unde v[j].dr=max ai v[j].dr<=v[i].st (j gasit cu cautare binara)
bool cmp(interval a,interval b){
    if(a.dr<b.dr)
        return true;
    if(a.dr>b.dr)
        return false;
    if(a.st<b.st)
        return true;
    else
        return false;
}
int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int cautabin(int val,int st,int dr){
    int mij,poz=0;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij].dr<=val){
            poz=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return poz;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    int i,j,n,rasp=0;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        j=cautabin(v[i].st,0,i-1);
        d[i]=max(d[i-1],d[j]+v[i].dr-v[i].st);
        //if(d[i]>rasp)
            //rasp=d[i];
    }
    fprintf(fout,"%d",d[n]);
    fclose(fin);
    fclose(fout);
    return 0;
}