Cod sursa(job #435058)

Utilizator encyEnciu Bogdan ency Data 6 aprilie 2010 20:47:20
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.44 kb
#include <stdio.h>
#include <stdlib.h>
int sort(const void *x, const void *y) {
  return (*(int*)x - *(int*)y);
}
void sorta(int a[][3],int n){
qsort(a,n,sizeof(int[3]),sort);
}
int max(int a[][2],int n,int x){
	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;
}

int calcul3(int c[][3],int n,int h,int u){
	int a[n][2];
	int i,k=0;
	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++;
						}
				}		
		}
		
	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 calcul2(int c[][3],int n,int h,int u){
	int a[n][2];
	int i;
	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];
						}
				}		
		}
	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 calcul(int c[][3],int n,int h,int u){
	int a[n][2];
	int i;
	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--;
						}
				}
		}
	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(){
	 int c[100000][3];
	 int i,n,h,gr,j,u;
         freopen("gutui.in", "r", stdin);
         freopen("gutui.out", "w", stdout); 
         scanf("%d",&n);
	 scanf("%d",&h);
	 scanf("%d",&u);
 	 for (i=0;i<n;i++) { 
     	 		scanf("%d",&c[i][0]);
			scanf("%d",&c[i][1]);
			c[i][2]=0;
	}
	gr=calcul3(c,n,h,u);
	printf("%d",gr);
	return 0;
}