Cod sursa(job #1857081)

Utilizator teodoramusatoiuTeodora Musatoiu teodoramusatoiu Data 25 ianuarie 2017 19:51:46
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n;

struct timpi
{
    int inc;
    int sf;
    int nr;
}v[100005];

bool cmp ( timpi x, timpi y) {
    if ( x.sf < y.sf )
      return 1;
    return 0;
}

int caut( int t, int n ) {
    int i = 0;
    int pas=1<<20;
    while (pas>0)
    {    if ( i + pas <= n && v[i + pas].sf <= t )
            i += pas;
        pas/=2;
    }
    return i;
}


int main()
{
    in>>n;
    int i;
    for (i=1;i<=n;i++)
        in>>v[i].inc>>v[i].sf;

    sort (v+1, v+n+1, cmp);

    for (i=1;i<=n;i++)
    {
        int x=caut(v[i].inc,n);
        v[i].nr=max(v[i-1].nr, v[x].nr+(v[i].sf-v[i].inc));
    }

    out<<v[n].nr;
    return 0;
}