Cod sursa(job #2702486)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 4 februarie 2021 11:58:03
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>
#define vt vector
#define INF 1e9
#define pb push_back
#define NMAX 100005

using namespace std;

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

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

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

    ans=0;
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d %d",&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("%d",ans);

    return 0;
}