Cod sursa(job #2362220)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 3 martie 2019 00:15:25
Problema Branza Scor 100
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, cant;
long long pret[DIM];

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();
        }
        deck.push_back(i);
        if (i - deck.front() > t){
            deck.pop_front();
        }
        sol += cant * (pret[deck.front()] + s*(i - deck.front()));
    }
    fout << sol;
    return 0;
}