Cod sursa(job #767880)

Utilizator SteveStefan Eniceicu Steve Data 15 iulie 2012 10:23:48
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>

using namespace std;

#define max(a, b) (a > b ? a : b)

typedef struct {
    int s;
    int f;
} cutzu;

int N;
cutzu v[100005];
int dp[100005];

inline int cmp (cutzu a, cutzu b) {
    //if (a.f == b.f) return a.s < b.s;
    return a.f < b.f;
}

void Citire () {
    ifstream fin ("heavymetal.in");
    fin >> N;
    for (int i = 0; i < N; i++)
        fin >> v[i].s >> v[i].f;
    fin.close ();
    sort (v, v + N, cmp);
}

int B_Search (int val) {
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && v[i + step].f <= val) i += step;
    return i;
}

void Business () {
    dp[0] = v[0].f - v[0].s;
    int a, j;
    for (int i = 1; i < N; i++)
    {
        a = B_Search (v[i].s);
        for (j = a; v[j].f <= v[i].s; j++);
        a = v[i].f - v[i].s + dp[j - 1];
        dp[i] = max (dp[i - 1], a);
    }
}

void Scriere () {
    ofstream fout ("heavymetal.out");
    fout << dp[N - 1];
    fout.close ();
}

int main () {
    Citire ();
    Business ();
    Scriere ();
    return 0;
}