Cod sursa(job #1618286)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 februarie 2016 19:20:19
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#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;
}