Cod sursa(job #2152316)

Utilizator dimi999Dimitriu Andrei dimi999 Data 5 martie 2018 13:51:13
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <bits/stdc++.h>
using namespace std;
FILE*f=fopen("branza.in","r");
ofstream fout("branza.out");

int v[100005],dq[100005];

int main()
{
    int n,s,t,st=1,dr=0,cant,pret,sum=0;
    int i=1;
    fscanf(f,"%d%d%d",&n,&s,&t);
    while(i<=n)
    {
        fscanf(f,"%d%d",&v[i],&pret);
        while(st<=dr&&(v[i]-s*(i-dq[dr]))<=v[dq[dr]])
            dr--;
        dq[++dr]=i;
        if(dq[st]==i-t)
            st++;
        sum=sum+pret*(v[dq[st]]+s*(i-dq[st]));
        i++;
    }
    fout<<sum;
    return 0;
}