Cod sursa(job #2328169)

Utilizator AndreiPanaAndrei Alexandru Pana AndreiPana Data 25 ianuarie 2019 14:49:40
Problema Branza Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <fstream>

using namespace std;

ifstream cin("branza.in");
ofstream cout("branza.out");

int main()
{
    long long pret[100000],k[100001],dq[100000], smin = 0;
    int n,t,s,st = 0,dr = 0;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++){
        cin>>pret[i]>>k[i];
    }
    for(int i=0;i<=n;i++){
        while(st<=dr && dq[st]==i-t){
            st++;
        }
        while(st<=dr && pret[i]<=pret[dq[dr]]+(i-dq[dr])*s){
            dr--;
        }
        dq[++dr]=i;
        smin += (pret[dq[st]]+s*(i-dq[st]))*k[i];
    }
    cout<<smin;
    return 0;
}