Pagini recente » Cod sursa (job #758174) | Cod sursa (job #2617295) | Cod sursa (job #2323564) | Cod sursa (job #2880733) | Cod sursa (job #1832145)
#include <cstdio>
typedef unsigned long long i64;
const int MAX_N = 100000;
struct Branza {
int pret, cant, poz;
}v[MAX_N];
Branza duba[MAX_N];
int st, dr;
int main() {
int n, s, t;
long long costmin;
FILE *fin = fopen("branza.in", "r");
fscanf(fin, "%d%d%d", &n, &s, &t);
for(int i = 0; i < n; ++i) {
fscanf(fin, "%d%d", &v[i].pret, &v[i].cant);
v[i].poz = i;
}
fclose(fin);
st = 0;
dr = -1;
costmin = 0LL;
for(int i = 0; i < n; ++i) {
if(i >= t && duba[st].pret == v[i - t].pret)
++st;
while(dr >= st && v[i].pret < duba[dr].pret + (i - duba[dr].poz) * s)
--dr;
++dr;
duba[dr] = v[i];
costmin = costmin + ((i64)duba[st].pret + (i - duba[st].poz) * s) * v[i].cant;
}
FILE *fout = fopen("branza.out", "w");
fprintf(fout, "%llu", costmin);
fclose(fout);
return 0;
}