Cod sursa(job #2544095)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 11 februarie 2020 19:24:13
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#define K 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long n,s,t,i,pret[K],nr,deq[K],p,u,sol,cantitate;
int main(){
    fin>>n>>s>>t;
    p=1; u=0;
    for(i=1;i<=n;i++){
        fin>>pret[i]>>cantitate;
        while(p<=u && pret[i]<=pret[deq[u]]+s*(i-deq[u]))
            u--;
        deq[++u]=i;
        if(i-deq[p]==t+1)
            p++;
        sol+=(pret[deq[p]]+s*(i-deq[p]))*cantitate;
    }
    fout<<sol;
    return 0;
}
/**in ziua i pot sa vand branza produsa in ziua i, sau depozitata din zilele i-1,i-2,..,i-t+1
calculez cu un deque in care tin max t elemente care e costul minim pt un kg:
pret[ziua i], pret[ziua i-1] + s, pret[ziua i-2] + 2*s,...,pret[ziua i-k+1] + (k-1)*s */