Cod sursa(job #1574993)

Utilizator tc_iuresiures tudor-cristian tc_iures Data 20 ianuarie 2016 23:47:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 100005;

int N, intMax;   // intMax = interval maxim
pair<int,int> Con[Nmax];
int best[Nmax];

void read()
{
    ifstream f("heavymetal.in");
    f >> N;
    for(int i = 1; i <= N; i ++)
    {
        f >> Con[i].first;
        f >> Con[i].second;
    }
    f.close();
}

bool compareByFinish(pair<int,int> x, pair<int,int> y)
{
    return(x.second < y.second);
}

void solve()
{
    sort(Con+1,Con+N+1,compareByFinish);
    int st, dr, m, poz;
    for(int i = 1; i <= N; i ++)
    {
        st = 1, dr = i-1;
        poz = 0;
        while(st <= dr)
        {
            m = (st+dr)>>1;
            if(Con[m].second <= Con[i].first)
            {
                poz = m;
                st = m+1;
            }
            else
            {
                dr = m-1;
            }
        }
        best[i] = max(best[i-1], best[poz] + Con[i].second-Con[i].first);
    }
}

void print()
{
    ofstream g("heavymetal.out");
    g << best[N];
    g.close();
}

int main()
{
    read();
    solve();
    print();
    return 0;
}