Cod sursa(job #767875)

Utilizator SteveStefan Eniceicu Steve Data 15 iulie 2012 10:03:32
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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];
long long 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 ind) {
    int i, step;
    for (step = 1; step < ind; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < ind && v[i + step].f <= val) i += step;
    return i;
}

void Business () {
    dp[0] = 1LL * v[0].f - v[0].s;
    long long a;
    for (int i = 1; i < N; i++)
    {
        a = 1LL * v[i].f - v[i].s + dp[B_Search (v[i].s, i)];
        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;
}