Cod sursa(job #430760)

Utilizator S7012MYPetru Trimbitas S7012MY Data 31 martie 2010 12:36:07
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#define maxint 999999
int N,a[200000];

struct oaie{
	long a,t;
}o[200000];

void upheap(int k) { 
    int val=a[k]; 
    a[0]=maxint; 
    while (a[k/2]<=val) { 
        a[k]=a[k/2]; 
        k/=2; 
    } 
    a[k]=val; 
} 


void downheap(int k) { 
    int j, val=a[k]; 
    while(k<=N/2) { 
        j=k+k; 
        if(j<N) 
            if(a[j]<a[j+1]) 
                j++; 
        if(val>=a[j]) break; 
        a[k]=a[j]; 
        k=j; 
    } 
    a[k]=val; 
} 

void insert (int val) { 
    N++; 
    a[N]=val; 
    upheap(N); 
} 

int remove() { 
    int val=a[1]; 
    a[1]=a[N]; 
    N--; 
    downheap(1); 
    return val; 
}

int main()
{
	long smax=0,n,x,l,i,d,tmax=0,j,z,k=0,ok=0;
	FILE *f=fopen("lupu.in","r");
	FILE *g=fopen("lupu.out","w");
	fscanf(f,"%ld %ld %ld",&n,&x,&l);
	if(l==0)
		for(i=0; i<n;i++) {
			fscanf(f,"%ld %ld",&d,&z);
			smax+=z;
		}
	else {
		for(i=0; i<n; i++) {
			fscanf(f,"%ld %ld",&d,&o[i].a);
			o[i].t=(x-d)/l+1;
			if(o[i].t>tmax) tmax=o[i].t;
		}
		for(i=tmax; i>=1; i--) {
			ok=0;
			for(j=0; j<n;j++)
				if(o[j].t==i) {
					insert(o[j].a);
					k++;
					ok=1;
				}
			if(ok) upheap(N);
			//z=remove(0);
			smax+=remove();
		}
	}
	fprintf(g,"%ld",smax);
	fclose(f);
	fclose(g);
	return 0;
}