Cod sursa(job #3123650)

Utilizator pinzaruliviuPinzaru Liviu-Vasile pinzaruliviu Data 25 aprilie 2023 00:07:04
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
using namespace std;
const int dim=100006;

ifstream f("branza.in");
ofstream g("branza.out");

long long int a[dim],b[dim],v[dim];

int main()
{
    int i,j,n,m,start=1,stop=1;
    long long int k,S=0,T=0,p;

    f>>n>>k>>T;

    f>>a[1]>>b[1];
    S+=a[1]*b[1];
    v[1]=1;

    for(i=2;i<=n;i++)
    {
        f>>a[i]>>b[i];

        if(i-v[start]==T+1)
            start++;

        while(start<=stop)
        {
            j=v[stop];
            p=a[j]+(i-j)*k;

            if(a[i]<=p)
            {
                stop--;
            }
            else
            {
                break;
            }
        }

        v[++stop]=i;

        j=v[start];
        p=a[j]+(i-j)*k;

        S+=b[i]*p;
    }

    g<<S;

    return 0;
}