Cod sursa(job #2760295)

Utilizator ioana2008vIoana Velniceru ioana2008v Data 24 iunie 2021 18:07:57
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N_MAX = 100001;
int val[N_MAX], n, s, t, p;
int deq[N_MAX], st = 0, dr = -1;
long long suma;

int main()
{
    ifstream fi ("branza.in");
    ofstream fo ("branza.out");
    fi >> n >> s >> t;
    t++;
    for (int i = 0; i < n; i++){
        fi >> val[i] >> p;
        if (st <= dr && deq[st] == i - t){
            st++;
        }
        while (st <= dr && val[i] <= val[deq[dr]] + s * (i - deq[dr])){
            dr--;
        }
        deq[++dr] = i;
        suma += p * (val[deq[st]] + s * (i - deq[st]));
    }
    fo << suma;
    fi.close();
    fo.close();
    return 0;
}