Cod sursa(job #2702492)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 4 februarie 2021 12:13:22
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
#define vt vector
#define INF 1e9
#define pb push_back
#define NMAX 100005
#define ll long long
using namespace std;

ll n,s,t,ans;
deque<ll>d;
vector<ll>c(NMAX);
vector<ll>p(NMAX);

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);

    scanf("%lli %lli %lli",&n,&s,&t);

    ans=0;
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%lli %lli",&c[i],&p[i]);
        while (!d.empty() && (c[d.back()] +(i-d.back())*s ) >= c[i])
            d.pop_back();
        while (!d.empty() && i-d.front() > t)
            d.pop_front();
        d.push_back(i);
        ans+=c[d.front()]*p[i] + p[i]*(i-d.front())*s;
    }

    printf("%lli",ans);

    return 0;
}