Cod sursa(job #440055)

Utilizator encyEnciu Bogdan ency Data 11 aprilie 2010 21:40:53
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.52 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100000 
typedef struct {
	unsigned long int *a;
	unsigned long int n;
	int k;
	} coada;
int sort(const void *x, const void *y) {
  return (*(int*)x - *(int*)y);
}
int sort1(const void *x, const void *y) {
  return (*(int*)y - *(int*)x);
}
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]),sort1);
}
void init(coada &q,unsigned long int x){
	q.a=(unsigned long int*)malloc(100000*sizeof(unsigned long int));
	q.n=0;
	q.k=100;
}
void add(coada &q,unsigned long int x){
//if(q.n+1>q.k) {          q.k=q.k+1000;
//		q.a=(unsigned long int*)realloc(q.a,q.k);
//	    }
q.a[q.n++]=x;
sorta1(q.a,q.n);
}
void del(coada &q){
for(unsigned long int i=0;i<q.n;i++)
q.a[i]=q.a[i+1];
q.n--;
}
void prin(coada q){
	printf("n=%ld\n",q.n);
	for(unsigned long int i=0;i<q.n;i++)
		printf("a %ld ",q.a[i]);
	printf("\n");
}
unsigned long int minim (unsigned long int a[][2], int n){
	unsigned long int m=a[0][0],j=-1;
	for(int i=0;i<n;i++)
		if(a[i][0]<m&&a[i][1]==0) {
			m=a[i][0];
			j=i;
		}
	a[j][1]=1;
	return m;
}	
unsigned long int gutui(unsigned long int c[][2],unsigned long int n,unsigned long int h,unsigned long int u){
	unsigned long int i,k=0,m=0,z;
	unsigned long int a[n][2];
	 int r=0;
	unsigned long int f[2];
	f[0]=1000000000;
	f[1]=1000000000;
	coada q;
	init(q,0);
	if(u>=h) {
		for(i=0;i<n;i++)
			if(m<c[i][1]&&c[i][0]<=h)
				m=c[i][1];
		return m; }	
	for(i=0;i<n;i++) 
		 if (c[i][0]>h)	 {
				 c[i][0]=0;
				 c[i][1]=0;}

	sorta2(c,n); 
	for(i=0;i<n;i++)
		if(k<=h-c[i][0])  { 
				m=m+c[i][1];
				printf("if m %ld\n " ,m);
				if (c[i][1]<f[0])
					f[0]=c[i][1];
				else
				if (c[i][1]<f[1])
					f[1]=c[i][1];
				printf("if %ld   %ld\n",f[0],f[1]);
				k=k+u;
				}
			else  if(c[i][1]>f[0])			
				         { m=m-f[0]; 
					f[0]=1000000000;
					m=m+c[i][1];
					printf("else m %ld \n" ,m);
		 	             	if (c[i][1]<f[1])
						f[0]=c[i][1];
						else  { 
						f[0]=f[1];
						f[1]=c[i][1];
						}
					printf("else %ld   %ld\n",f[0],f[1]);		
					}   				
return m;
}
int main(){
	 unsigned long int c[100000][2];
	 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=gutui(c,n,h,u);
	printf("%ld\n",gr);
	return 0;
}