Pagini recente » Cod sursa (job #1535839) | Rating Stefan Rizescu (rizesql) | Cod sursa (job #2248668) | Cod sursa (job #2604830) | Cod sursa (job #209198)
Cod sursa(job #209198)
#include<stdio.h>
struct branza {long long c,p;} b[100011];
long long ok,i,n,m,s,t,aux,N,M[100011],P[100011];
long long h[100011];
void up(long long poz){
long long c,p;
c=poz;
p=poz>>1;
while( (h[c] < h[p]) && c!=1 ){
aux=h[c];
h[c]=h[p];
h[p]=aux;
aux=P[P[c]];
P[P[c]]=P[P[p]];
P[P[p]]=aux;
c=p;
p=c>>1;
}
}
void down(long long poz){
long long p,c;
p=poz;
c=p<<1;
while(c<=N){
if(h[c] > h[c+1] && c<N )
c++;
if(h[p] > h[c]){
aux=h[c];
h[c]=h[p];
h[p]=aux;
aux=P[P[c]];
P[P[c]]=P[P[p]];
P[P[p]]=aux;
p=c;
c=p<<1;
}
else
break;
}
}
int main(){
FILE *f=fopen("branza.in","r");
fscanf(f,"%lld %lld %lld",&n,&s,&t);
for(i=1;i<=n;i++){
fscanf(f,"%lld %lld",&b[i].c,&b[i].p);
P[i]=i;
}
fclose(f);
t++;
h[1]=b[1].c+s*(n-1);
N=1;
M[1]=b[1].c;
for(i=2;i<=t;i++){
N++;
h[N]=b[i].c+s*(n-i);
up(N);
M[i]=h[1]-(s*(n-i));
}
long long q=1;
for(i=t+1;i<=n;i++,q++){
M[i]=b[i].c;
//inlocuim elem de pe pozitia q din sir care se afla pe poz P[q] in heap
if( h[P[q]]<b[i].c+s*(n-i))
//cobor
ok=1;
else
ok=0;
h[P[q]]=b[i].c+s*(n-i);
if(ok==1)
down(P[q]);
if(ok==0)
up(P[q]);
M[i]=h[1]-(s*(n-i));
}
long long sol=0;
for(i=1;i<=n;i++)
sol+=(b[i].p*M[i]);
FILE *g=fopen("branza.out","w");
fprintf(g,"%lld",sol);
fclose(g);
return 0;
}