Pagini recente » Istoria paginii runda/carnedecal/clasament | Cod sursa (job #1572183) | Istoria paginii runda/ip/clasament | Cod sursa (job #898241) | Cod sursa (job #1618286)
#include <iostream>
#include <cstdio>
using namespace std;
int pret[100001];
int deq[100001];
int dst, ddr;
void adaugaInDeque(int x, int i, int pretDepozit);
void scoateBranzaVeche(int i, int t);
int main()
{
FILE *fin = fopen("branza.in", "r");
FILE *fout = fopen("branza.out", "w");
int n, pretDepozit, t, cerere, suma = 0;
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(pret[i], i, pretDepozit);
suma += (pret[deq[dst]] + (i - deq[dst]) * pretDepozit) * cerere;
scoateBranzaVeche(i, t);
}
fprintf(fout, "%d", suma);
return 0;
}
void adaugaInDeque(int x, int i, int pretDepozit){
while(dst <= ddr && x <= 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;
}