Cod sursa(job #2498025)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 23 noiembrie 2019 13:39:29
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct formatie{
    int a,b;
};

const int inf = 1000000003;
formatie f[100004];
int DP[100004];
int DPstart[100004];

bool cmp(formatie x,formatie y){
    if(x.b < y.b){
        return 1;
    }else{
        return 0;
    }
}

//bool binsrc(int )

int main()
{
    int n,i,aux,sol,j,durata,dr,st,mid;
    fin>>n;
    for(i = 1; i <= n ; i++){
        fin>>f[i].a>>f[i].b;
    }
    sort(f+1,f+n+1,cmp);
    for(i = 1; i <= n; i++){
        aux = 0;
        j = i-1;
        sol = 0;
        dr = i-1;
        st = 1;
        durata = f[i].b - f[i].a;
        while(st <= dr){
            mid = (st+dr)>>1;
            if(DPstart[mid] <= f[i].a){
                sol = DP[mid];
                st = mid+1;
            }else{
                dr = mid-1;
            }
        }
        aux = sol;
        if(DP[i-1] < aux + durata){
            DP[i] = aux + durata;
            DPstart[i] = f[i].b;
        }else{
            DP[i] = DP[i-1];
            DPstart[i] = DPstart[i-1];
        }
    }
    fout<<DP[n]<<endl;
    return 0;
}