Pagini recente » Cod sursa (job #2701089) | Cod sursa (job #3288398) | Cod sursa (job #2967496) | Cod sursa (job #3136442) | Cod sursa (job #209476)
Cod sursa(job #209476)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct adsaa{long long c,p;}b[100011];
long long aux,h[100011],P[100011],n,s,t,i,N;
long long m[100011];
void up(long long poz){
int c,p;
c=poz;
p=c>>1;
while( c!=1 && (h[c] < h[p]) ){
aux=h[c];
h[c]=h[p];
h[p]=aux;
aux=P[P[c]];
P[P[p]]=P[P[p]];
P[P[p]]=aux;
c=p;
p=c>>1;
}
}
void down(long long poz){
int c,p;
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[p]]=P[P[p]];
P[P[p]]=aux;
p=c;
c=p<<1;
}
else
break;
}
}
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);
N=1;
m[1]=b[1].c;
h[1]=b[1].c + s*(n-1);
long long R;
for(i=2;i<=n;i++){
if(i-(t+1) > 0){
R=b[i].c + s*(n-i);
if(R > h[P[i-(t+1) ]]){
h[P[i-(t+1) ]]=R;
down(P[i-(t+1) ]);
}
else{
h[P[i-(t+1) ]]=R;
up(P[i-(t+1) ]);
}
}
else{
N++;
h[N]=b[i].c + s*(n-i);
up(N);
}
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,"%d",sol);
fclose(g);
return 0;
}