Cod sursa(job #436266)

Utilizator encyEnciu Bogdan ency Data 8 aprilie 2010 13:48:53
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.96 kb
#include <stdio.h>
#include <stdlib.h>
int sort(const void *x, const void *y) {
  return (*(int*)x - *(int*)y);
}
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[][2],unsigned long int n,unsigned long int x){
	unsigned long int i,maxim=0;
	for(i=0;i<n;i++){
		if (a[i][0]==x)
			if(maxim<a[i][1])
				maxim=a[i][1];
		}
	return maxim;
}

unsigned long int calcul3(unsigned long int c[][3],unsigned long int n,unsigned long int h,unsigned long int u){
	unsigned long int a[n][2];
	unsigned long int i,k=0;
	unsigned long int x=0;
	sorta(c,n);
	
	/*for(i=0;i<n;i++)		
		printf("a[%d]= %d/%d\n",i,c[i][0],c[i][1]);*/
	for(i=0;i<n;i++) {
		a[i][0]=h/u-c[i][0]/u;
		a[i][1]=c[i][1];		
		}
	/*for(i=0;i<n;i++) {
		printf("gutuia %d grad %d greut %d\n",i,a[i][0],a[i][1]);
		}*/
	for(i=0;i<n;i++){
		//printf("k=%d\n",k);
		if(i!=0) 
			   if(a[i][0]!=a[i-1][0]&&k<a[i][0])  {
				x=max(a,n,a[i-1][0]);
				a[i][1]=x+a[i][1]; 
		//		printf("a %d %d %d\n",k,i,a[i][1]);
				k++;
				}
				else  {
					if(a[i][0]>1) {
						if(max(a,n,a[i][0]-1)<a[i][1])
							{	
							a[i][1]=a[i-1][1]+a[i][1];
		//					printf("caz 2 a %d %d\n",i,a[i][1]);
							k++;
							}
						 else  {
						x=max(a,n,a[i-1][0]);					
						a[i][1]=x+a[i][1];
						k++;
						}
					 	}
						else  {
						//x=max(a,n,a[i-1][0]);
						a[i][1]=x+a[i][1];
						k++;
						}
				}		
		}
		
	unsigned long int m=0;		
	for(i=0;i<n;i++) {
		if(a[i][1]>m)
			m=a[i][1];
		//printf("gutuia %d grad %d greut %d\n",i,a[i][0],a[i][1]);
		}
	return m;
}
unsigned long int calcul2(unsigned long int c[][3],unsigned long int n,unsigned long int h,unsigned long int u){
	unsigned long int a[n][2];
	unsigned long int i;
	unsigned long int x=0,k=0;
	sorta(c,n);
	for(i=0;i<n;i++) {
		a[i][0]=c[n-i-1][0];
		a[i][1]=c[n-i-1][1];
		}
	for(i=0;i<n;i++)		
		//printf("a[%d]= %d/%d\n",i,a[i][0],a[i][1]);
	for(i=0;i<n;i++) 
		a[i][0]=h/u-a[i][0]/u;
	for(i=0;i<n;i++) {
		//printf("gutuia %d grad %d greut %d\n",i,a[i][0],a[i][1]);
		}
	
	for(i=n-1;i>=0;i--){
		if(i!=n-1) 
			   if(a[i][0]!=a[i+1][0]&&k<a[i][0])  {
				x=max(a,n,a[i+1][0]);
				a[i][1]=x+a[i][1]; 
				//printf("a %d %d %d\n",k,i,a[i][1]);
				}
				else  {
					if(a[i][0]>1) {
						if(max(a,n,a[i][0]-1)<a[i][1])
							{	
							a[i][1]=a[i+1][1]+a[i][1];
							//printf("caz 2 a %d %d\n",i,a[i][1]);
							k++;
							}
						 else  {
						x=max(a,n,a[i+1][0]);					
						a[i][1]=x+a[i][1];
						
						}
					 	}
						else  {
						//x=max(a,n,a[i+1][0]);
						a[i][1]=x+a[i][1];
						}
				}		
		}
	unsigned long int m=0;		
	for(i=0;i<n;i++) {
		if(a[i][1]>m)
			m=a[i][1];
		//printf("gutuia %d grad %d greut %d\n",i,a[i][0],a[i][1]);
		}
	return m;
}
unsigned long int calcul(unsigned long int c[][3],unsigned long int n,unsigned long int h,unsigned long int u){
	unsigned long int a[n][2];
	unsigned long int i;
	unsigned long int x=0,k=0;
	sorta(c,n);
	//for(i=0;i<n;i++)
		//printf("a[%d]= %d/%d\n",i,c[i][0],c[i][1]);
	for(i=n-1;i>=0;i--){
		a[i][0]=h/u-c[i][0]/u;
		if(i==n-1)
			a[i][1]=c[i][1];
			else 
			   if(a[i][0]!=a[i+1][0]&&k<a[i][0])  {
				x=max(a,n,a[i+1][0]);
				a[i][1]=x+c[i][1]; 
		//		printf("a %d %d %d\n",k,i,a[i][1]);
				}
				else  {
				if(a[i][0]>1) {
						a[i][1]=a[i+1][1]+c[i][1];
		//				printf("caz 2 a %d %d\n",i,a[i][1]);
						k++;
						}
						else { 
						a[i][1]=x+c[i][1];
						if(a[i][1]<a[i-1][1])
							k--;
						}
				}
		}
	unsigned long int m=0;		
	for(i=0;i<n;i++) {
		if(a[i][1]>m)
			m=a[i][1];
		//printf("gutuia %d grad %d greut %d\n",i,a[i][0],a[i][1]);
		}
	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][0]);
			scanf("%ld",&c[i][1]);
			c[i][2]=0;
	}
	gr=calcul3(c,n,h,u);
	printf("%ld",gr);
	return 0;
}