Cod sursa(job #206566)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 7 septembrie 2008 18:53:27
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>

#define NMAX 100000
#define MMAX 131072
struct br{int c,q;};
struct nod{int x,p;};
br v[NMAX+1];
long long c[NMAX+1];
nod q[MMAX+10];
int m;

void refac(int vf,int nn){
int poz=vf,copil=2*vf,gata=0;
nod t=q[vf];
while(copil<=nn&&!gata){
	if(copil<nn&&q[copil].x>q[copil+1].x) ++copil;
	if(t.x>q[copil].x){
		q[poz]=q[copil];
		poz=copil;
		copil=2*poz;
		}
	else gata=1;
	}
q[poz]=t;
}

void nou(){
int copil=m,parinte=m/2;
nod t;
while(parinte>=1&&q[parinte].x>q[copil].x){
	t=q[copil];q[copil]=q[parinte];q[parinte]=t;
	copil=parinte;
	parinte=copil/2;
	}
}
void elim(){
if(m){
	q[1]=q[m];
	--m;
	refac(1,m);
	}
else q[1]=q[0];
}

int main(){
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
int n,s,t,i,j,li,pc;
int ce,gata;
long long total;
scanf("%d%d%d",&n,&s,&t);
for(i=1;i<=n;++i) scanf("%d%d",&v[i].c,&v[i].q);

for(i=1;i<=n;++i){
	m++;
	q[m].x=v[i].c+(n-i)*s;
	q[m].p=i;
	nou();
	li=i-t;
	if(li<1) li=1;
	gata=0;
	while(!gata){
		pc=q[1].p;
		if(pc<li) elim();
		else {ce=q[1].x;gata=1;}
		}
	c[i]=ce-(n-i)*s;
	}
total=0L;
for(i=1;i<=n;++i) total+=c[i]*v[i].q;
printf("%lld",total);
return 0;
}