Cod sursa(job #437052)

Utilizator encyEnciu Bogdan ency Data 9 aprilie 2010 11:37:13
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.37 kb
#include <stdio.h>
#include <stdlib.h>
int sort(const void *x, const void *y) {
  return (*(int*)y - *(int*)x);
}
void sorta(unsigned long int a[][3],unsigned long int n){
qsort(a,n,sizeof(unsigned long int[3]),sort);
}

unsigned long int max(unsigned long int a[][3],unsigned long int n,unsigned long int x){
	unsigned long int i,j,maxim=0;
	for(i=0;i<n;i++){
		if (a[i][1]==x&&a[i][2]==0)
			if(maxim<a[i][0]) {
				maxim=a[i][0];
				j=i;}
		}
	return j;
}

unsigned long int calcul3(unsigned long int c[][3],unsigned long int n,unsigned long int h,unsigned long int u){
	unsigned long int i,k=0;
	unsigned long int x=0,m=0,min=0;
	for(i=0;i<n;i++)
		c[i][1]=h/u-(c[i][1]-1)/u;
	for(i=0;i<n;i++)
	//	printf("inaltimi %ld\n" ,c[i][1] );
	for(i=0;i<n;i++) 
		if(min<c[i][1])
			min=c[i][1]; //nr max de alegeri 
	if (min>n)
		min=n;
	//printf("min=%ld\n",min);
	for(i=0;i<n;i++)
		for(k=0;k<c[i][1];k++) 
			c[max(c,n,c[i][1])][2]=1;
	sorta(c,n);
	for(i=0;i<min;i++)
		if(c[i][2]==1)
			m=m+c[i][0];
	return m;
}
int main(){
	 unsigned long int c[100000][3];
	 unsigned long int i,n,h,gr,j,u;
         freopen("gutui.in", "r", stdin);
         freopen("gutui.out", "w", stdout); 
         scanf("%ld",&n);
	 scanf("%ld",&h);
	 scanf("%ld",&u);
 	 for (i=0;i<n;i++) { 
     	 		scanf("%ld",&c[i][1]);
			scanf("%ld",&c[i][0]);
			c[i][2]=0;
	}
	gr=calcul3(c,n,h,u);
	printf("%ld",gr);
	return 0;
}