Cod sursa(job #2038451)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 13 octombrie 2017 18:01:10
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct pereche{
    int start;
    int stop;
    int timp;
}trupe[100001];

bool cmp(pereche a, pereche b){
    if(b.stop>a.stop)
        return 1;
    if(b.stop==a.stop && b.start>a.start)
        return 1;
    return 0;
}

int cauta(int li, int ls, int val){
    if(ls==0)
        return 0;
    int mij;
    while(li<=ls){
        mij=(li+ls)/2;
        if(trupe[mij].stop==val)
            return mij;
        else if(trupe[mij].stop<val)
            li=mij+1;
        else
            ls=mij-1;
    }
    return ls;
}

int main()
{
    FILE *fin, *fout;
    int n,a,b,i,time,x;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d %d\n",&a,&b);
        trupe[i].start=a;
        trupe[i].stop=b;
    }
    sort(trupe,trupe+n+1,cmp);
    time=0;
    for(i=1;i<=n;i++){
        x=cauta(1,i-1,trupe[i].start);
        trupe[i].timp=trupe[x].timp+(trupe[i].stop-trupe[i].start);
        time=time>trupe[i].timp?time:trupe[i].timp;
    }
    fprintf(fout,"%d\n",time);
    fclose(fin);
    fclose(fout);
    return 0;
}