Pagini recente » Cod sursa (job #1202160) | Cod sursa (job #264692) | Cod sursa (job #2373361) | Cod sursa (job #684286) | Cod sursa (job #209188)
Cod sursa(job #209188)
#include<stdio.h>
#define INF 1000000
struct branza {int c,p;} b[100011];
int ok,i,n,m,s,t,aux,N,M[100011],P[100011];
int h[100011];
void up(int poz){
int 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(int poz){
int p,c,c1,c2;
p=poz;
c1=p<<1;
c2=c1+1;
if( h[c2]<h[c1] && c2<=N ){
c=c2;
}
else
c=c1;
while( h[p]>h[c] && (c<=N) ){
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;
c1=p<<1;
c2=c1+1;
if( h[c2]<h[c1] && c2<=N ){
c=c2;
}
else
c=c1;
}
}
int main(){
FILE *f=fopen("branza.in","r");
fscanf(f,"%d %d %d",&n,&s,&t);
for(i=1;i<=n;i++){
fscanf(f,"%d %d",&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++){
M[i]=b[i].c;
if(M[i] > ( h[1]-(s*(n-i)) ) )
M[i]=h[1]-(s*(n-i));
N++;
h[N]=b[i].c+s*(n-i);
up(N);
}
int 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));
}
int sol=0;
for(i=1;i<=n;i++)
sol+=(b[i].p*M[i]);
FILE *g=fopen("branza.out","w");
fprintf(g,"%d",sol);
fclose(g);
return 0;
}