Cod sursa(job #2708969)

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

using namespace std;

int n, s, t;
long long c[100100];
long long p[100100];
int dq[100100];
long long ans;

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

int main()
{
    fin >> n >> s >> t;
    t++;
    for(int i = 1; i <= n; i ++)
    {
        fin >> c[i] >> p[i];
    }
    int st = 0, dr = -1;
    for(int i = 1; i <= n; i ++)
    {
        if(st <= dr && dq[st] == i - t)
            st++;
        while(st <= dr && c[dq[dr]] + (i - dq[dr]) * s >= c[i])
            dr--;
        dq[++dr] = i;
        ans = ans + c[dq[st]] * p[i] + s * (i - dq[st]) * p[i];
    }
    fout << ans << '\n';
}