Cod sursa(job #435182)

Utilizator stef2nStefan Istrate stef2n Data 7 aprilie 2010 00:00:37
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 0.7 kb
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream in("gutui.in");
ofstream out("gutui.out");

int N, H, U;
vector < pair <int, int> > gutui;
vector <int> best;
int maxim = 0;


int main() {
    in >> N >> H >> U;

    gutui.resize(N);
    for (int i = 0; i < N; ++i)
        in >> gutui[i].first >> gutui[i].second;
    sort(gutui.begin(), gutui.end());

    best.resize(N);
    for (int i = 0, j = 0; i < N; ++i) {
        if (gutui[i].first > H) break;

        while (j < i && gutui[j].first + U <= H)
            maxim = max(maxim, best[j++]);

        best[i] = maxim + gutui[i].second;
    }

    out << *max_element(best.begin(), best.end()) << "\n";

    return 0;
}