Cod sursa(job #2084225)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 8 decembrie 2017 20:09:10
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
#define MAXN 100000

struct Interval{
    int st, dr;
}v[1 + MAXN];
bool cmp(Interval A, Interval B){
    return A.dr < B.dr;
}
int d[1 + MAXN];

int main(){
    FILE*fi,*fo;
    fi=fopen("heavymetal.in","r");
    fo=fopen("heavymetal.out","w");

    int n;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++)
        fscanf(fi,"%d%d", &v[i].st, &v[i].dr);
    std::sort(v + 1, v + n + 1, cmp);

    for(int i = 1; i <= n; i++){
        int ok = 0;
        if(v[1].dr <= v[i].st){
            int st = 1, dr = n - 1;
            while(dr - st > 1){
                int m = (st + dr) / 2;
                if(v[m].dr > v[i].st)
                    dr = m - 1;
                else
                    st = m;
            }
            if(v[dr].dr <= v[i].st)
                ok = dr;
            else
                ok = st;
        }
        d[i] = std::max(d[i - 1], v[i].dr - v[i].st + d[ok]);
    }
    fprintf(fo,"%d", d[n]);
    fclose(fi);
    fclose(fo);
    return 0;
}