Cod sursa(job #2717993)

Utilizator Mihnea_DumitruDumitru Mihnea-Andrei Mihnea_Dumitru Data 8 martie 2021 12:05:55
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <fstream>

using namespace std;

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

const int N=100001;
int dq[N],c[N];

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