Pagini recente » Cod sursa (job #140894) | Cod sursa (job #1809268) | Cod sursa (job #770658) | Istoria paginii runda/vot | Cod sursa (job #1618312)
#include <iostream>
#include <cstdio>
using namespace std;
int pret[100001];
int deq[100001];
int dst, ddr;
void adaugaInDeque(int i, int pretDepozit);
void scoateBranzaVeche(int i, int t);
int main()
{
FILE *fin = fopen("branza.in", "r");
FILE *fout = fopen("branza.out", "w");
long long int suma = 0;
int n, pretDepozit, t, cerere;
fscanf(fin, "%d%d%d", &n, &pretDepozit, &t);
dst = 1;
ddr = 0;
for(int i = 1; i <= n; ++i){
fscanf(fin, "%d%d", &pret[i], &cerere);
adaugaInDeque(i, pretDepozit);
scoateBranzaVeche(i, t);
suma += (1LL * pret[deq[dst]] + (i - deq[dst]) * pretDepozit) * cerere;
}
fprintf(fout, "%lld", suma);
return 0;
}
void adaugaInDeque(int i, int pretDepozit){
while(dst <= ddr && pret[i] <= pret[deq[ddr]] + (i - deq[ddr]) * pretDepozit)
--ddr;
deq[++ddr] = i;
}
void scoateBranzaVeche(int i, int t){
while(dst <= ddr && i - deq[dst] > t)
++dst;
}