Cod sursa(job #2873146)

Utilizator Liviu_Silviucont de incercari Liviu_Silviu Data 18 martie 2022 18:46:35
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
char buff[4096];
int pbuf=4095;
void readbuff(){
    pbuf=0;fin.read(buff,4095);
}
int citire(){
    int nr=0;
    if(pbuf==4095){
        readbuff();
    }
    while(buff[pbuf]<'0'||buff[pbuf]>'9'){
        pbuf++;
        if(pbuf==4095){
            readbuff();
        }
    }
    while(buff[pbuf]>='0'&&buff[pbuf]<='9'){
        nr=nr*10+buff[pbuf]-'0';pbuf++;
        if(pbuf==4095){
            readbuff();
        }
    }
    return nr;
}
struct interv{
    int st,dr;
}v[100005];
bool cmp(interv x,interv y){
    return x.dr<y.dr;
}
int dp[100005],max1[100005];
int main()
{
    int n;n=citire();
    for(int i=1;i<=n;i++){
        v[i].st=citire();v[i].dr=citire();
    }sort(v+1,v+n+1,cmp);int val1,val2,mij,val=0;
    for(int i=1;i<=n;i++){
        val1=1;val2=i-1;val=-1;
        while(val2>=val1){
            mij=(val1+val2)/2;
            if(v[mij].dr<=v[i].st){
                val=mij;val1=mij+1;
            }
            else{
                val2=mij-1;
            }
        }
        dp[i]=max1[val]+v[i].dr-v[i].st;
        max1[i]=max(max1[i-1],dp[i]);
    }fout<<max1[n]<<'\n';
    return 0;
}