Pagini recente » Cod sursa (job #2963648) | Clasament pregatire_oji_4 | Cod sursa (job #1153462) | Cod sursa (job #2343798) | Cod sursa (job #209482)
Cod sursa(job #209482)
#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],p2[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;
p2[P[c]]=P[p];
p2[P[p]]=P[c];
aux=P[c];
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;
p2[P[c]]=P[p];
p2[P[p]]=P[c];
aux=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;
p2[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);
P[i]=p2[i-(t+1) ];
p2[i]=p2[i-(t+1) ];
if(R > h[P[i-(t+1) ]]){
h[p2[i-(t+1) ]]=R;
down(p2[i-(t+1) ]);
}
else{
h[p2[i-(t+1) ]]=R;
up(p2[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,"%lld",sol);
fclose(g);
return 0;
}