Cod sursa(job #3181809)

Utilizator mariusharabariMarius Harabari mariusharabari Data 7 decembrie 2023 22:55:19
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>
#include <deque>
using namespace std;

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

deque<int> d;
int n, t, s, v[100005], vp[100005];

int main(){
    fin>>n>>s>>t;
    int i, a;
    for(i=0;i<n;i++){
        fin>>a>>vp[i];
        v[i]=i*s-a;
    }

    long long cmin=0;

    for(i=0;i<n;i++){
        while(!d.empty()&&v[i]>=v[d.back()])
            d.pop_back();
        if(!d.empty()&&d.front()==i-t)
            d.pop_front();
        d.push_back(i);

        cmin+=(long long)(((long long)i*s-v[d.front()])*vp[i]);
        //cout<<(i*s-v[d.front()])*vp[i]<<endl;
    }

    fout<<cmin<<endl;
    return 0;
}