Cod sursa(job #439899)

Utilizator encyEnciu Bogdan ency Data 11 aprilie 2010 20:18:09
Problema Gutui Scor 70
Compilator cpp Status done
Runda teme_upb Marime 1.43 kb
#include <stdio.h>
#include <stdlib.h>
int sort(const void *x, const void *y) {
  return (*(int*)y - *(int*)x);
}
void sorta2(unsigned long int a[][2],unsigned long int n){
qsort(a,n,sizeof(unsigned long int[2]),sort);
}
unsigned long int minim (unsigned long int a[][2], int n,unsigned long int u){
	unsigned long int m=1000000000,j=-1;
	for(int i=0;i<n;i++)
		if(a[i][0]<m&&a[i][1]==0) {
			m=a[i][0];
			j=i;
		}
	if (u>m)
	 	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];
	unsigned long int r=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; 
		 }	
	sorta2(c,n); 
	for(i=0;i<n;i++)
		if(k<=h-c[i][0])  { 
			m=m+c[i][1];
			a[r][0]=c[i][1];
			a[r][1]=0;
			r++;
			k=k+u;
		 }
		     else  {
			    z=minim(a,r,c[i][1]); 
			    if(c[i][1]>z) { 
				m=m-z; 	           
				m=m+c[i][1];
				a[r][0]=c[i][1];
				a[r][1]=0;
				r++;				
			     }  
		      }  				
				
	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;
}