Cod sursa(job #2907141)

Utilizator TODEToderita Mihai TODE Data 28 mai 2022 21:32:23
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <deque>
#include <utility>
using namespace std;

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

const int N = 1e5 + 1;
int v[N] , kg;
deque<int> dq;
long long sum;
int main(){
    int n , s , t;
    cin>>n>>s>>t;
    //t++; // nr zile pana se strica
    for(int i = 1 ; i <= n ; i++){
        cin>>v[i]>>kg;
        while(!dq.empty() && dq.front() < i - t) // s-a stricat
            dq.pop_front();
        while(!dq.empty() && v[dq.back()] + (i - dq.back()) * s > v[i])
            dq.pop_back();
        dq.push_back(i);
        sum = sum + (v[dq.front()] + s * (i - dq.front()) * kg);
        //cout<<v[dq.front()].first<<' '<<i - dq.front()<<' '<<v[i].second<<'\n';
    }
    cout<<sum;
}