Cod sursa(job #2610346)

Utilizator harrygirleaHarry Girlea harrygirlea Data 4 mai 2020 19:07:22
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>

using namespace std;

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

int v[100002], dq[100002];

int main() {
    int n, s, t, st, dr, c;
    long long brinza=0;
    in>>n>>s>>t;
    t++;
    st=0;
    dr=-1;
    for (int i = 0; i < n; i++ ) {
        in>>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;
        brinza += 1LL * c * ( v[dq[st]] + 1LL * ( i - dq[st] ) * s );
    }
    out<<brinza;
    return 0;
}