Cod sursa(job #631740)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 9 noiembrie 2011 18:44:15
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.94 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

vector <pair <int, int> > gutui;
priority_queue <int> heap;
int n, u, h, s;

void read() {
  FILE *f = fopen("gutui.in", "r");
  int x, y;

  fscanf(f, "%d%d%d", &n, &h, &u);

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

  fclose(f);
}

void solve() {
  int hcrt = h, i = 0;

  while(hcrt - u >= gutui[0].first)
    hcrt -= u;

  while (1) {
    if(gutui[i].first > hcrt || i >= n) {
      if(!heap.empty()) {
	s += heap.top();
	heap.pop();
      }
      hcrt += u;
      if (hcrt > h)
  	break;
    }
    if (i < n && gutui[i].first <= hcrt) {
      heap.push(gutui[i].second);
      i ++;
    }
  }
}

void write() {
  FILE *g = fopen("gutui.out", "w");
  fprintf(g, "%d\n", s);
  fclose (g);
}

int main() {

  read();

  sort (gutui.begin(), gutui.end());

  solve ();
  write ();

  return 0;
}