Cod sursa(job #2561350)

Utilizator Davla2Stancu Vlad Davla2 Data 28 februarie 2020 19:05:28
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>

using namespace std;

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

const int N=100001;

struct pret{
    int c,p;
};

pret v[N];
int dq[N];
long long sum;

int main()
{
    int n,s,t,dr,st;
    in>>n>>s>>t;
    for(int i=0; i<n; i++)
    {
        in>>v[i].p>>v[i].c;
    }
    dr=-1;
    st=0;
    for(int i=0; i<n; i++)
    {
        if(st<=dr && dq[st]==i-t)
        {
            st++;
        }
        while(st<=dr && v[i].p<=v[dq[dr]].p+(i-dq[dr])*s)
        {
            dr--;
        }
        dq[++dr]=i;
        sum+=(v[dq[st]].p+(i-dq[st])*s)*v[i].c;
    }
    out<<sum;
    return 0;
}