Cod sursa(job #439025)

Utilizator stefanrStefan Ruseti stefanr Data 11 aprilie 2010 11:50:51
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.42 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct
{
	int h, g;
} gutuie;

gutuie v[100000];

int cmp(const void *a, const void *b)
{
	gutuie x, y;
	x = *(gutuie *) a;
	y = *(gutuie *) b;
	if (x.h == y.h) return y.g - x.g;
	return x.h - y.h;
}

int max(int a, int b)
{
    if (a > b) return a;
    return b;
}


int main()
{
	int n, h, u, i, j;
	
	FILE *fin, *fout;
	fin = fopen("gutui.in", "rt");
	fout = fopen("gutui.out", "wt");
	
	fscanf(fin, "%i %i %i", &n, &h, &u);
		
	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;
	}
		
	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;
}