Cod sursa(job #2610304)

Utilizator RaduNRadu Negovan RaduN Data 4 mai 2020 18:35:05
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int v[100002], dq[100002];
int main() {
    int n, s, t, st, dr, c;
    long long cost=0;
    f>>n>>s>>t;
    t++;
    st=0;
    dr=-1;
    for (int i=0; i<n; i++) {
        f>>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;
        cost+=1LL*c*(v[dq[st]]+1LL*(i-dq[st])*s);
    }
    g<<cost;
    return 0;
}