Cod sursa(job #3126725)

Utilizator HaiduculAndrei Popa Haiducul Data 6 mai 2023 21:59:42
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("branza.in"); ofstream g("branza.out");
long long zile,S,T;
long long suma=0,i,k;
deque <int> deq;
int main()
{   f>>zile>>S>>T;
    long long p[zile+1];
    for (i=1; i<=zile; ++i)
    {   f >> p[i] >> k;
        ///eliminam branza expirata
        while(deq.size()>0 and deq.front()<i-T){
            deq.pop_front();
        }
        ///daca pretul este prea mare
        while(deq.size()>0 and ((i-deq.back())*S + p[deq.back()]) > p[i]){
            deq.pop_back();
        }
        deq.push_back(i);
        suma += k * (p[deq.front()] + S * (i - deq.front()));
    }
    g<<suma;
    f.close(); g.close();
    return 0;
}