Cod sursa(job #2708811)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 19 februarie 2021 14:24:34
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[100100], dq[100100];
int st = 0, dr = -1;
long long rez = 0;
int n, s, t, c;

int main()
{
    fin >> n >> s >> t;
    t++;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i] >> c;

        if (st <= dr && dq[st] == i - t)
        {
            st++;
        }

        while (st <= dr && v[dq[dr]] + (i - dq[dr])*s >= v[i])
        {
            dr--;
        }

        dq[++dr] = i;

        rez += (long long)c * (v[dq[st]] + (long long)(i - dq[st]) * s);
    }
    fout << rez;
    return 0;
}