Cod sursa(job #439535)

Utilizator stefanrStefan Ruseti stefanr Data 11 aprilie 2010 16:53:16
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct
{
	int h, g;
} gutuie;

bool cmp(const gutuie &a, const gutuie &b)
{
    return (a.h < b.h);
}

int main()
{
	int n, h, u, i, j;
	
	FILE *fin, *fout;
	fin = fopen("lupu.in", "rt");
	fout = fopen("lupu.out", "wt");
	
	fscanf(fin, "%i %i %i", &n, &h, &u);
	vector<gutuie> v(n);
    vector<gutuie>::iterator itV;	
	for (i = 0; i < n; i++)
	{
		fscanf(fin, "%i %i", &(v[i].h), &(v[i].g));
		v[i].h = (h - v[i].h) / u + 1;
		if(v[i].h < 0) v[i].h = 0;
	}
	
    std::sort(v.begin(), v.end(), cmp);
    
	//qsort(v, n, sizeof(gutuie), cmp);
    
    int s = 0;
    vector<int> a;
    vector<int>::iterator it;
    j = v[n-1].h;
    i = n-1;
    while (i >= 0 && j > 0)
    {
        if (j == v[i].h)
        {
            a.push_back(v[i].g);
            push_heap(a.begin(), a.end());
            i--;
            continue;
        }
        j--;
        if (a.empty()) continue;
        pop_heap(a.begin(), a.end());
        s += a.back();
        a.pop_back();
    }
    while (j > 0 && !a.empty())
    {
        pop_heap(a.begin(), a.end());
        s += a.back();
        a.pop_back();
        j--; 
    }
    fprintf(fout, "%i", s);
    
    fclose(fin);
	fclose(fout);
	return 0;
}