Cod sursa(job #2362216)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 3 martie 2019 00:07:45
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

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

long long n, s, t, i, sol;
long long pret[DIM], cant;

deque <long long> deck;

int main(){
    fin >> n >> s >> t;
    for (i=1; i<=n; i++){
        fin >> pret[i] >> cant;
        while (!deck.empty() && pret[i] <= pret[deck.back()] + s*(i - deck.back())){
            deck.pop_back();
        }
        if (i - deck.front() > t){
            deck.pop_front();
        }
        deck.push_back(i);
        sol += cant * (pret[deck.front()] + s*(i - deck.front()));
    }
    fout << sol;
    return 0;
}