Cod sursa(job #2585226)

Utilizator DooMeDCristian Alexutan DooMeD Data 18 martie 2020 20:23:11
Problema Heavy metal Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
int n,i,dp[100005],mx,j,l,pmax;
struct cv {
    int in,sf;
} v[100005];

bool comp(cv a,cv b) {
    if(a.sf>b.sf) return false;
    if(a.sf==b.sf and a.in>b.in) return false;
    return true;
}

int binar(int caut) {
    int p=0;
    for(int k=pmax; k>=0; k--)
        if(v[p+(1<<k)].sf<=caut) p=p+(1<<k);
    return p;
}

int main() {
    f >> n;
    while( (1<<(pmax+1)) <=n ) pmax++;
    for(i=1; i<=n; i++)
      f >> v[i].in >> v[i].sf;
    sort(v+1,v+n+1,comp);
    dp[1]=v[1].sf-v[1].in;
    for(i=2; i<=n; i++)
        dp[i]=max(dp[i-1],dp[binar(v[i].in)]+v[i].sf-v[i].in) ;
    g << dp[n];
    return 0;
}