Cod sursa(job #2274392)

Utilizator valeriucaraselCarasel Valeriu valeriucarasel Data 1 noiembrie 2018 19:10:30
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <iostream>
#include <fstream>

using namespace std;

int dq[100005];

int main()
{
    ifstream in("branza.in");
    ofstream out("branza.out");
    int n,t,s;
    in>>n>>s>>t;
    int c[n+5],p[n+5];
    for (int i=0;i<n;i++)
    {
        in>>c[i]>>p[i];
    }
    int st=0,dr=-1;
    long long total=0;
    for (int i=0;i<n;i++)
    {
        if (i>=t && dq[st]==i-t)
        {
            st++;
        }
        while (st<=dr && c[i]<=c[dq[dr]]+s*(i-dq[dr]))
        {
            dr--;
        }
        dq[++dr]=i;
        total+=(long)p[i]*(c[dq[st]]+s*(i-dq[st]));
    }
    out<<total;
    in.close();
    out.close();
    return 0;
}