Cod sursa(job #437986)

Utilizator encyEnciu Bogdan ency Data 10 aprilie 2010 13:01:12
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.92 kb
#include <stdio.h>
#include <stdlib.h>
 unsigned long int minim(unsigned long int a,unsigned long int b){
	return a<b ? a:b; 
	}
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);
}
void sorta1(unsigned long int a[],unsigned long int n){
qsort(a,n,sizeof(unsigned long int),sort);
}
void sorta2(unsigned long int a[][2],unsigned long int n){
qsort(a,n,sizeof(unsigned long int[2]),sort);
}
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,max=0 ,q,z,t;
	unsigned long int a[h/u][h/u],idx[h/u],j,d[n];
	for(i=0;i<n;i++) 
		 if (c[i][1]>h)	 {
				 c[i][0]=0;
				 c[i][1]=2;}
	for(i=0;i<n;i++) 
		c[i][1]=h/u-(c[i][1]-1)/u;
	
	
	
	for(i=0;i<n;i++) {
	//	printf("%ld, %ld\n",c[i][0],c[i][1]);
		if(x<c[i][1]) 
			x=c[i][1];
    		
		}
	//printf("min %ld",x);
	for(i=0;i<x+1;i++)
		idx[i]=0;
	for(i=0;i<x+1;i++)
		for(j=0;j<x+1;j++)
			a[i][j]=0; 
	for(i=0;i<n;i++) {
		a[c[i][1]][idx[c[i][1]]++]=c[i][0];
                }
	for(i=0;i<x+1;i++)
		sorta1(a[i],idx[i]);
	for(i=0;i<x+1;i++)
		if (idx[i]>i) idx[i]=i;
	//for(i=0;i<x+1;i++)      {
	//	for(j=0;j<idx[i];j++)
	//		printf("%ld ",a[i][j]);
	//	printf("\n");
	//	}
	 
	max=0;q=0;k=0;t=0;
	
	
	/*for(j=0;j<x+1;j++){
		m=0;q=-1;
		for(i=0;i<x+1;i++) 
				if(i+j<=x&&idx[i+j]>i)
					if(a[i+j][i]>m) {
						m=a[i+j][i];
						q=i+j;t=i;
			                           }
		
		max=max+m;
		if(m==0)
			  {if (q==-1&&j!=0) k++;}
		   else a[q][t]=0;
		
		printf("j=%ld  m %ld max %ld\n" ,j,m,max);
		}
	*/ 
	/*printf("wtf\n");
	for(i=1;i<x+1;i++){
		m=0;q=-1;
		printf("idx[%ld]=%ld\n",i,idx[i]);
		for(j=idx[i];j>=0;j--) {
			//printf("a[%ld][%ld]",i,j);
			if(a[i][j]>m) {
				m=a[i][j]; 
		                q=i;t=j;
				}
			}
		max=max+m;
		if(m==0)
			  {if (q==-1&&j!=0) k++;}
		   else a[q][t]=0;
		
		printf("j=%ld  m %ld max %ld\n" ,j,m,max);
		}
	
	for(i=0;i<x+1;i++)      {
		for(j=0;j<idx[i];j++)
			printf("%ld ",a[i][j]);
		printf("\n");
		}
	z=0;
	for(i=0;i<x+1;i++)      
		for(j=0;j<idx[i];j++)
			if(a[i][j]>0) {
				d[z]=a[i][j];
				z++;
				}
	printf("%ld  %ld \n ",z,k);
	sorta1(d,z);
	for(i=0;i<minim(z,k);i++)
		max=max+d[i];	*/

	z=0;
	for(i=0;i<x+1;i++)      
		for(j=0;j<idx[i];j++)
			if(a[i][j]>0) {
				d[z]=a[i][j];
				z++;
				}
		
	sorta1(d,z);
	max=0;
	//for(i=0;i<x;i++) 
	//	printf("%ld \n",d[i]);
	for(i=0;i<x;i++) 
		max=max+d[i];
			                      
	return max;
}
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\n",gr);
	return 0;
}