Cod sursa(job #906241)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 6 martie 2013 17:19:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <algorithm>
#define NMax 100005
using namespace std;

struct Interval{int left, right, profit;};
int N, DP[NMax];
Interval Int[NMax];

bool cmp (Interval X, Interval Y) {

    return X.right < Y.right;

}
int BinSearch(int left, int right, int Val) {

    int pos = 0;
    while (left <= right) {

        int mid = (left + right) / 2;
        if (Int[mid].right <= Val)
            left = mid + 1, pos = mid;
        else
            right = mid - 1;
        }

    return pos;
}
void Solve() {

    int i,j;

    sort(Int + 1, Int + N + 1,cmp);

    for (i = 1; i <= N; ++i) {
        j = BinSearch(1, i - 1, Int[i].left);
        DP[i] = max(DP[i - 1], DP[j] + Int[i].profit);
        }

}
void Read() {

    freopen("heavymetal.in", "r", stdin);
    scanf("%d", &N);

    for (int i = 1; i <= N; ++i) {
        scanf("%d %d", &Int[i].left, &Int[i].right);
        Int[i].profit=Int[i].right-Int[i].left;
        }

}
void Print() {

    freopen("heavymetal.out", "w", stdout);
    printf("%d\n", DP[N]);

}
int main() {

    Read();
    Solve();
    Print();

    return 0;

}