Cod sursa(job #139224)

Utilizator wefgefAndrei Grigorean wefgef Data 19 februarie 2008 20:33:33
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

const int Nmax = 100005;

int N;
pair<int, int> T[Nmax];
vector<int> v;
int Best[2*Nmax];

void ReadData() {
     assert(scanf("%d", &N) == 1);
     assert(1 <= N && N <= 100000);
     for (int i = 0; i < N; ++i) {
         assert(scanf("%d %d", &T[i].first, &T[i].second) == 2);
         assert(1 <= T[i].first && T[i].first <= 1000000000);
         assert(1 <= T[i].second && T[i].second <= 1000000000);
     }
}

void Normalizeaza() {
     for (int i = 0; i < N; ++i) {
         v.push_back(T[i].first);
         v.push_back(T[i].second);
     }
     sort(v.begin(), v.end());
     v.resize(unique(v.begin(), v.end()) - v.begin());
     
     for (int i = 0; i < N; ++i) {
         T[i].first = lower_bound(v.begin(), v.end(), T[i].first) - v.begin();
         T[i].second = lower_bound(v.begin(), v.end(), T[i].second) - v.begin();
     }
}

void Solve() {
     Normalizeaza();
     sort(T, T+N);
     Best[T[0].second] = v[T[0].second] - v[T[0].first];
     for (int i = 1; i < N; ++i) {
         for (int j = T[i-1].first+1; j <= T[i].first; ++j)
             Best[j] = max(Best[j], Best[j-1]);
         Best[T[i].second] = max(Best[T[i].second], Best[T[i].first] + v[T[i].second] - v[T[i].first]);         
     }
     for (int i = T[N-1].first+1; i < int(v.size()); ++i)
         Best[i] = max(Best[i], Best[i-1]);
     printf("%d\n", Best[int(v.size())-1]);
}

int main() {
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    
    ReadData();
    Solve();
}