Cod sursa(job #438262)

Utilizator encyEnciu Bogdan ency Data 10 aprilie 2010 16:56:51
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.72 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 w=0,i,k=0;
	unsigned long int x=0,m=0,min=0,max=0 ,q,z,t;
	unsigned long int b[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]=0;}
	for(i=0;i<n;i++) 
		 if (c[i][1]>0)   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\n",x);
	for(i=0;i<x+1;i++)
		idx[i]=0; 
	for(i=0;i<n;i++) {
		if (c[i][1]!=0) {
			b[c[i][1]][idx[c[i][1]]]=c[i][0]; 
			//printf("b[%ld][%ld],%ld, %ld\n",c[i][1],idx[c[i][1]],b[c[i][1]][idx[c[i][1]]],c[i][0]);
			idx[c[i][1]]++;}
		
		
                }
	//for(i=0;i<x+1;i++)      {
	//	printf("linia %ld",i);
	//	for(j=0;j<x;j++)
	//	        	printf(" %ld ",b[i][j]);
	//	printf("\n");
	//	}
	for(i=0;i<x;i++)
		sorta1(b[i],idx[i]);
	for(i=0;i<x;i++)
		if (idx[i]>i) idx[i]=i;
	for(i=0;i<x+1;i++)
		w=w+idx[i];
	///for(i=0;i<x+1;i++)      {
	//	for(j=0;j<idx[i];j++)
	//		printf("%ld ",b[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<x+1;i++)
		printf("i=%ld idx%ld \n",i,idx[i]);
	printf("wtf\n");
	for(i=1;i<x+1;i++){
		m=0;q=-1;
		printf("idx[%ld]=%ld\n",i,idx[i]);
		if(idx[x]>0)
		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);
		}*/
	if(w<x+1) {
		for(i=0;i<x+1;i++)      
		for(j=0;j<idx[i];j++)
			max=max+b[i][j];
		return max;
		} 
	 for(i=1;i<x;i++) 
		if(b[i][idx[i]-1]>0&&b[i-1][0]>0&&(idx[i]>1||i-1==1)) { 
	//			printf("i=%ld idx%ld \n",i,idx[i]);
	//			printf("%ld  > %ld\n" ,b[i][idx[i]-1],b[i-1][0]);
			if(b[i][idx[i]-1]>b[i-1][0])
				 
                	          b[i-1][0]=0; 
				else 	
				idx[i]--;}
 	//for(i=0;i<x+1;i++)
	//	printf("i=%ld idx%ld \n",i,idx[i]);
//	sleep(6);
	
	//for(i=0;i<x+1;i++)      {
	//	for(j=0;j<idx[i];j++)
	//		printf("%ld ",b[i][j]);
	//	printf("\n");
	//	}
	z=0;
	for(i=0;i<x+1;i++)      
		for(j=0;j<idx[i];j++)
			if(b[i][j]>0) {
				d[z]=b[i][j];
				z++;
				}
	//printf("%ld  %ld \n ",z,k);
	sorta1(d,z);
	for(i=0;i<minim(n,x);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;
}