Cod sursa(job #498700)

Utilizator GulyanAlexandru Gulyan Data 5 noiembrie 2010 19:09:07
Problema Lupul Urias si Rau Scor 76
Compilator c Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	long g, r;
}Fr;

int cmp(const void *a, const void *b) {
	if( ((Fr*)a)->r != ((Fr*)b)->r )
		return ((Fr*)b)->r - ((Fr*)a)->r;
	return ((Fr*)b)->g - ((Fr*)a)->g;
}

void merge(long *v, long m, long d, long n) {
	if(d <= m)
		return;
	long *v2 = (long *)malloc(n * sizeof(long));
	long i = 0, j = m + 1, k = 0;
	while(k < n && i <= m && j <= d)
		if(v[i] > v[j])
			v2[k++] = v[i++];
		else
			v2[k++] = v[j++];
	while(k < n && i <= m)
		v2[k++] = v[i++];
	while(k < n && j <= d)
		v2[k++] = v[j++];
	for(i = 0; i < k; i++)
		v[i] = v2[i];
	free(v2);
}

int main() {
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	long n, s, k, i, j;
	scanf("%ld%ld%ld", &n, &s, &k);
	Fr *v = (Fr*)(malloc(n * sizeof(Fr)));
	long *buff, *origBuff = buff = (long *)malloc(n * sizeof(long));
	for(i = 0; n--;) {
		scanf("%ld%ld", &(v[i].r), &(v[i].g));
		if(v[i].r > s)
			continue;
		v[i].r = (s - v[i].r) / k;
		i++;
	}
	qsort(v, n = i, sizeof(Fr), cmp);
	long m, vf = -1, max = 0;
	for(i = 0, j = s / k; j >= 0; j--) {
		m = vf;
		while(i < n && v[i].r >= j)
			buff[++vf] = v[i++].g;
		merge(buff, m, vf, j + 1);
		if(vf > j)
			vf = j;
		if(vf >= 0) {
			max += buff[0];
			--vf;
			++buff;
		}
	}	
	printf("%ld\n", max);
	free(v);
	free(origBuff);
	fclose(stdout);
	return 0;
}