Cod sursa(job #2378753)

Utilizator Mihnea_BranzeuMihnea Branzeu Mihnea_Branzeu Data 12 martie 2019 16:37:22
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct dezmat{
  int a,b;
}v[100002];
int d[100002];
const int L=30;
int n;

bool cmp(dezmat a,dezmat b){
  return a.b<b.b;
}

int caut1(int x)
{
    int r,pas;
    r=0;
    pas=1<<L;
    while(pas!=0)
    {
        if(r+pas<=n && v[r+pas].b<=x)
            r+=pas;
        pas/=2;
    }

    return r;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i].a>>v[i].b;
    sort(v+1,v+n+1,cmp);
    int valoros;
    for(int i=1; i<=n; i++)
    {
        valoros=v[i].b-v[i].a+d[caut1(v[i].a)];
        d[i]=max(d[i-1],valoros);
    }
    int vmax=-1;
    for(int i=1;i<=n;i++)
      vmax=max(vmax,d[i]);
    fout<<vmax;
    return 0;
}