Cod sursa(job #2036128)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 10 octombrie 2017 12:51:00
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
/*int pret[100000];
int main()
{
    int n,s,t,i,j,S=0,st=0,m,cant;
    bool b;
    cin>>n>>s>>t;
    for(i=0;i<n;i++)
    {
        cin>>pret[i]>>cant;
        m=pret[i];
        b=0;
        for(j=i-st;j>0;j--)
            if(pret[i-j]*j*s<m)
                m=pret[i-j]*j*s,b=1;
            else if(!b)
                st++;
        S+=m*cant;
        if(i-st==t)
            st++;
    }
    cout<<S;
    return 0;
}*/
int arr[5000001];
int d[5000001];
int st=0,dr=-1,i,n,k,pr;
void solve()
{
    if(st<=dr&&d[st]==i-k-1)
        st++;
    while(st<=dr&&arr[i]<=arr[d[dr]]+(i-d[dr])*pr)
        dr--;
    d[++dr]=i;
}
int main()
{
    long long s=0,cant;
    in>>n>>pr>>k;
    for(i=1;i<=n;i++)
    {
        in>>arr[i]>>cant;
        solve();
        s+=(arr[d[st]]+(i-d[st])*pr)*cant;
    }
    out<<s;
    return 0;
}