Cod sursa(job #438860)

Utilizator Bogdan.CirsteaCirstea Bogdan-Ionut Bogdan.Cirstea Data 11 aprilie 2010 01:47:14
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.97 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>


struct Gutui {
  int h, w;

  friend bool operator<(Gutui const& a, Gutui const& b) {
    return a.h < b.h; // or (a.h == b.h and a.w < b.w); 
  }
  friend bool operator>(Gutui const& a, Gutui const& b) {
    return b < a;
  }
  friend std::ostream& operator<<(std::ostream& s, Gutui const& v) {
    s << '(' << v.h << ", " << v.w << ')';
    return s;
  }
};

/*
template<class T, class C, T C::*M>
struct sum {
  T operator()(T const& cur, C const& next) { return cur + next.*M; }
};
*/

int solve(std::vector<Gutui> gutui, int H, int U) {



  std::sort(gutui.begin(), gutui.end(), std::greater<Gutui>()); //>

  int picked_weight = 0;
  std::vector<int> available_weights;

  int top;
  int offset = H % U;
  if (offset == U) top = 0;
  else top = offset - U;


  while ((gutui.size() or available_weights.size()) and top <= H) {

    if (available_weights.size()) {
      picked_weight += available_weights.front(); 
      std::pop_heap(available_weights.begin(), available_weights.end());
      available_weights.pop_back();
      top += U;
    }
    else {
      top += U * std::max(1, (gutui.back().h - top) / U); 
    }

    while (gutui.size() and gutui.back().h <= top) {
      available_weights.push_back(gutui.back().w);
      std::push_heap(available_weights.begin(), available_weights.end());
      gutui.pop_back();
    }
  }

  return picked_weight;
}




int main() {

	FILE* fd1;
	FILE* fd2;
	
	fd1=fopen("gutui.out", "w");
	fd2=fopen("gutui.in", "r");

	int numargutui, height, step;
	fscanf(fd2, "%i %i %i", &numargutui, &height, &step);

	Gutui data[numargutui]; 
	int i;
	for (i = 0; i < numargutui; i++)
		fscanf(fd2, "%i %i ", &(data[i].h), &(data[i].w));

 	 std::vector<Gutui> v (data, data + numargutui); // nombergutui sau +-1?
  	int actual = solve(v, height, step);
	fprintf(fd1, "%i ", actual);

	fclose(fd2);	
	fclose(fd1);
}