Pagini recente » Cod sursa (job #1752398) | Cod sursa (job #1255665) | Cod sursa (job #2401088) | Cod sursa (job #2138345) | Cod sursa (job #811883)
Cod sursa(job #811883)
#include<stdio.h>
#define maxn 100005
FILE*f=fopen("branza.in","r");
FILE*g=fopen("branza.out","w");
int n,s,T;
int deque[maxn],front,back,P[maxn];
long long D[maxn];
int main () {
fscanf(f,"%d %d %d",&n,&s,&T);
int pret,cerere;
int front = 1,back = 0;
for ( int i = 1 ; i <= n ; ++i ){
fscanf(f,"%d %d",&pret,&cerere); P[i] = pret;
while ( front <= back && 1LL*(i-deque[back])*s + P[deque[back]] >= pret ){
deque[back--] = 0;
}
deque[++back] = i;
if ( deque[front] < i-T ){
++front;
}
D[i] = D[i-1] + 1LL*cerere*( 1LL*(i-deque[front])*s + P[deque[front]] );
}
fprintf(g,"%lld\n",D[n]);
fclose(f);
fclose(g);
return 0;
}