Cod sursa(job #440036)

Utilizator oana.vasiuVasiu Oana-Alexandra oana.vasiu Data 11 aprilie 2010 21:34:59
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.72 kb
#include <stdio.h>
#include <stdlib.h>
int sort1(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]),sort1);
}

void add (unsigned long int a[],unsigned long int gr,unsigned long int &r){
	if(gr<=a[0]) {
		for(int i=r;i>0;i--) 
 			a[i]=a[i-1];
		a[0]=gr;
		r++;
		return;
 		}
	if(gr>=a[r-1]) {
		a[r]=gr;
		r++;
		return;
 		}
	for(int i=0;i<r;i++)
		if(a[i]<=gr&&gr<=a[i+1]) {
			for(int j=r;j>i+1;j--)
				a[i]=a[i-1];
			a[i+1]=gr;
			r++;
			return;
			}
	
}
void print(unsigned long int a[],unsigned long int n){
	for(int i=0;i<n;i++)
		printf(" %ld ",a[i]);
	printf("\n");
}
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;
	unsigned long int r=0,t=0;
	a=(unsigned long int *)malloc(n*sizeof(unsigned long int));
	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];
				add(a,c[i][1],r);
				//print(a,r);
				k=k+u;
				}
			else  if(c[i][1]>a[0])
									
				         { 
					   m=m-a[0];
				          a=a+1; 	           
					  m=m+c[i][1];
					   add(a,c[i][1],r);
				//		print(a,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;
}