Cod sursa(job #2863096)

Utilizator Theo14Ancuta Theodor Theo14 Data 6 martie 2022 12:38:29
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<bits/stdc++.h>
#define int long long
using namespace std;

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

int n,s,t,dq[100004];

struct elem
{
    int c,p;
}v[100004];

signed main()
{
    int i,frontt,backk,sum=0;
    f>>n>>s>>t;
    for(i=1;i<=n;i++)
    {
        f>>v[i].c>>v[i].p;
    }
    frontt=1;
    backk=0;
    for(i=1;i<=n;i++)
    {
        while(frontt<=backk && v[i].c<=v[dq[backk]].c + s*(i-dq[backk]))
            backk--;
        backk++;
        dq[backk]=i;
        if(i-dq[frontt]+1>t)
            frontt++;
        sum+=((v[dq[frontt]].c + (i-dq[frontt])*s)*v[i].p);
    }
    g<<sum;
    return 0;
}