Cod sursa(job #437232)

Utilizator encyEnciu Bogdan ency Data 9 aprilie 2010 15:13:09
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.23 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++)
		c[i][1]=h/u-(c[i][1]-1)/u;
	for(i=0;i<n;i++)
		if(x<c[i][1]) 
			x=c[i][1];
	//printf("min %ld",x);
	for(i=0;i<h/u;i++)
		idx[i]=0;
	for(i=0;i<h/u;i++)
		for(j=0;j<h/u;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<h/u;i++)
		sorta1(a[i],idx[i]);
	for(i=0;i<h/u;i++)
		if (idx[i]>i) idx[i]=i;
	//for(i=0;i<h/u;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);
		}
//	for(i=0;i<h/u;i++)      {
	//	for(j=0;j<idx[i];j++)
	//		printf("%ld ",a[i][j]);
	//	printf("\n");
		}
	z=0;
	for(i=0;i<h/u;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];			                      
	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",gr);
	return 0;
}