Cod sursa(job #2888378)

Utilizator RosianuRobertRosianu Robert RosianuRobert Data 11 aprilie 2022 00:14:56
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long v[100001],Deq1[100001],cerere[100001],s;
int taxa,k,first,i,n,last;
int main()
{
    f>>n>>taxa>>k;
    for(i=1; i<=n; i++)
    {
        f>>v[i]>>cerere[i];
    }
    s=0;
    first=1;
    last=0;
    for(i=1; i<=n; i++)
    {
        while(v[i]<=v[Deq1[last]] + taxa * (i - Deq1[last]))
        {
            if(first > last)
                break;
            else
                last--;
        }
        last++;
        Deq1[last]=i;
        if(Deq1[first] == i - k)
            first++;
        s+=(1LL*v[Deq1[first]] + 1LL*taxa * (i - Deq1[first])) * cerere[i];
    }
    g<<s;
    return 0;
}