Cod sursa(job #1857629)

Utilizator tgm000Tudor Mocioi tgm000 Data 26 ianuarie 2017 14:46:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct ceva{int st,dr;};
ceva v[100001];
int d[100001];
bool cmp(ceva a,ceva b){
    if(a.dr<b.dr)
        return true;
    else
        return false;
}
int main(){
    int n,i,maxi,l1,l2,poz,m;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].st,&v[i].dr);
    sort(v+1,v+n+1,cmp);
    maxi=0;
    for(i=1;i<=n;i++){
        l1=1;
        l2=i;
        poz=0;
        while(l1<=l2){
            m=(l1+l2)/2;
            if(v[m].dr<=v[i].st){
                poz=m;
                l1=m+1;
            }else
                l2=m-1;
        }
        d[i]=maxi;
        if(d[poz]+v[i].dr-v[i].st>d[i]){
            d[i]=d[poz]+v[i].dr-v[i].st;
            maxi=d[poz]+v[i].dr-v[i].st;
        }
    }
    printf("%d",maxi);
    return 0;
}