Cod sursa(job #1117183)

Utilizator StexanIarca Stefan Stexan Data 23 februarie 2014 11:03:51
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

struct Event{
    int begining, ending;
};

#define NMAX 10010

int N,Maximum,DP[NMAX];
Event Events[NMAX];

bool cmp(Event A,Event B) {
    return A.ending < B.ending;
}

void Read(){
    f>>N;
    for (int i = 1; i <= N; i++) {
        f>>Events[i].begining>>Events[i].ending;
    }
}

int Search(int point)
{
    int left = 0,right = point ,middle;
    while (left <= right) {
        middle = (left + right)/2;
        if (Events[middle].ending > Events[point].begining) {
            right = middle - 1;
        }else{
            left = middle + 1;
        }
    }
    return (left+right)/2;
}

void Solve(){
    sort(Events+1, Events+N+1, cmp);
    DP[1] = Events[1].ending - Events[1].begining;
    Maximum = DP[1];
    int position,value;
    for (int i = 2; i <= N; i++) {
        position = Search(i);
        value = Events[i].ending - Events[i].begining;
        if (DP[position] + value > Maximum) {
            Maximum = DP[position] + value;
        }
        DP[i] = Maximum;
    }
}

void Write(){
    g<<Maximum;
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}