Cod sursa(job #434802)

Utilizator encyEnciu Bogdan ency Data 6 aprilie 2010 16:19:37
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.88 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;
	int x=0,k=0;
	sorta(c,n);
	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])  {
				x=max(a,n,a[i+1][0]);
				a[i][1]=x+c[i][1];
				}
				else { 
					a[i][1]=x+c[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 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++)
		//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);
	//j=calcul3(c,n,h,u);
	printf("%d",gr);
	return 0;
}