Cod sursa(job #2731838)

Utilizator GhiuzanuEdward Ghiuzan Ghiuzanu Data 28 martie 2021 13:49:56
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <iostream>
#include <fstream>
using namespace std;

#define Nmax 100005

long long  n;
long long s, t;
long long c[Nmax];
long long Q[Nmax], qe, qb;
long long ret;

int main() {
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    long long i;
    long long p;
    fin >> n >> s >> t;
    qe = 0;
    qb = 1;
    for (i = 1; i <= n; ++i) {
        cin >> c[i] >> p;
        while (qe >= qb && (i - Q[qe]) * s + c[Q[qe]] >= c[i]) --qe;
        Q[++qe] = i;
        if (i - Q[qb] > t) ++qb;
        ret += p * (c[Q[qb]] + (i - Q[qb]) * s);
    }
    fout << ret;
    return 0;
}