Cod sursa(job #2734162)

Utilizator betybety bety bety Data 31 martie 2021 14:46:52
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
typedef long long ll;
deque<pair<ll,ll> > dq;
const ll lim=1e5+4;
ll p[lim];
ll c[lim];
ll m[lim];
ll ans;
int main()
{
    ll n,s,t;
    in>>n>>s>>t;
    for(ll i=1;i<=n;++i)
        in>>c[i]>>p[i];
    for(ll i=1;i<=n;++i)
    {
        while(!dq.empty() and dq.back().first>=c[i]+(n-i)*s)
            dq.pop_back();
        dq.push_back({c[i]+(n-i)*s,i});
        if(dq.front().second<i-t)
            dq.pop_front();
        m[i]=dq.front().first-(n-i)*s;
        ans+=m[i]*p[i];
    }
    out<<ans<<'\n';
    return 0;
}