Pagini recente » Cod sursa (job #2291977) | Cod sursa (job #3335086) | Cod sursa (job #625062) | Cod sursa (job #622049) | Cod sursa (job #2174808)
#include <stdio.h>
#include <stdlib.h>
#define N 100000
int c[N], p[N], dq[N];
int prim = 0, ultim = -1;
int main() {
FILE *fin, *fout;
int n, s, t, i, j;
long long ctot = 0LL, aux;
fin = fopen( "branza.in", "r" );
fout = fopen( "branza.out", "w" );
fscanf( fin, "%d%d%d", &n, &s, &t );
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d%d", &c[i], &p[i] );
if ( i - dq[prim] == t + 1 )
prim++;
while ( ultim >= 0 && c[i] <= ( c[dq[ultim]] + s * ( i - dq[ultim] ) ) )
ultim--;
dq[ultim + 1] = i;
ultim++;
aux = i - dq[prim];
aux *= s;
aux += c[dq[prim]];
aux *= p[i];
ctot += aux;
}
fprintf( fout, "%lld", ctot );
fclose( fin );
fclose( fout );
return 0;
}