Cod sursa(job #430803)

Utilizator S7012MYPetru Trimbitas S7012MY Data 31 martie 2010 13:04:09
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

vector <long> h;

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

int main()
{
	long smax=0,n,x,l,i,d,tmax=0,j,z;
	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--) {
			for(j=0; j<n;j++)
				if(o[j].t==i) {
					if(o[j].a) {
						h.push_back(o[j].a);
						push_heap (h.begin(),h.end());
					}
				}
				if(o[j-1].a) {
					smax+=h.front();
					pop_heap(h.begin(),h.end());
					h.pop_back();
				}
		}
	}
	fprintf(g,"%ld",smax);
	fclose(f);
	fclose(g);
	return 0;
}