Cod sursa(job #429118)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 29 martie 2010 20:35:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("lupu.in","r");
FILE *g=fopen("lupu.out","w");
int i,j,n,x,l,d,tmax,a[100002],nr,k,y,maxim,p;
struct oaie{
	  int lana;
	  int t;
} oi[100002];
long long total;
int cmp(oaie a, oaie b){
	return(a.t>b.t);
}
void combheap(int i, int u){
	  int s,d;
	  while(2*i<=u)
	  { maxim=a[i]; //maximul este elmentul curent
		  s=2*i; //stanga
		  d=2*i+1; //dreapta
		if(maxim<a[s]) //maximul este elementul din stanga
		  { maxim=a[s];
		    p=s;
		  }
		if(maxim<a[d] && d<=u) //maximul este elmentul din deapta
		  { maxim=a[d];
		    p=d;
		  }
		if(maxim!=a[i]){
			d=a[i];
			a[i]=maxim;
			a[p]=d;
			i=p;
		}
		else 
			break;
	  }
}
int main(){
nr=0;k=0;
//citim
fscanf(f,"%d%d%d",&n,&x,&l);
for(i=1;i<=n;i++){
	fscanf(f,"%d%d",&d,&oi[i].lana);
	if(x-d>=0){
		   oi[i].t=1+(x-d)/l;
	}
		
	else oi[i].t=0;
	if(oi[i].t>tmax)
		tmax=oi[i].t;
}
//sortam vectorul in functie de timpul maxim la care lupul poate ajunge oaia i
sort(oi+1,oi+n+1,cmp);
i=0;nr=0;
for(j=tmax;j>=1;j--){ //parcurgem timpii
	while(i<n&&oi[i+1].t==j) //adaugam toate oile care au timpii egali cu j
    {i++;
	y=oi[i].lana;
	nr++;
	k=nr;
	while(k>1&&y>a[k/2]){  
			a[k]=a[k/2];
			  k=k/2;
		}
		a[k]=y;  //adaugam in heap
    }
if(nr>0){
total+=(long long)a[1]; 	//adaugam maximul la total

// aici greseai la eliminarea din heap
//tu faceai ceva de genul
//a[1]=0;combheap(1,nr);nr--;
//este gresit fiindca tu facand astfel nu adegi elementul maxim in varf


int t=a[1];a[1]=a[nr];//eliminam elementul maxim
a[nr]=t;nr--;
combheap(1,nr); //reactualizam heapul
}
}
fprintf(g,"%lld",total);
return 0;
}