Pagini recente » Cod sursa (job #2014885) | Cod sursa (job #2470918) | Cod sursa (job #1442374) | Cod sursa (job #1751245) | Cod sursa (job #206566)
Cod sursa(job #206566)
#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;
}