Cod sursa(job #631133)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 7 noiembrie 2011 02:34:16
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.13 kb
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX_N 1000010

using namespace std;

int n, h, u;

class my_comp {
  public:
  bool operator () (const pair <int, int> &a, const pair <int, int> &b) {
    return (a.second < b.second);
  }
};

int main () {
  priority_queue <pair <int, int>, vector < pair <int, int> >, my_comp> heap;
  vector <pair <int, int> > gutui;
  pair <int, int> temp;
  int x, y;

  freopen ("gutui.in", "r", stdin);
  freopen ("gutui.out", "w", stdout);

  scanf ("%d %d %d", &n, &h, &u);
  for (int i = 0; i < n; i ++) {
    scanf ("%d %d", &x, &y);
    gutui.push_back (make_pair (x, y));
  }

  sort (gutui.begin (), gutui.end (), greater <pair <int, int> > ());

  for (int i = 0; i < n; i ++) {
    if (heap.size () * u + gutui[i].first <= h)
      heap.push (gutui[i]);
    if (heap.size () && (heap.size () - 1) * u + gutui[i].first <= h && 
	heap.top ().second < gutui[i].second) {
      heap.pop ();
      heap.push (gutui[i]);
    }
  }

  int s = 0;
  while (!heap.empty ()) {
    s += heap.top ().second;
    heap.pop ();
  }

  printf ("%d\n", s);
  return 0;
}