Cod sursa(job #1806913)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 15 noiembrie 2016 20:30:55
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
long long sol;
int c[maxN],v[maxN],n,s,t,m[maxN];
deque<int> q;
int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&v[i]);
    }
    m[1]=c[1];
    q.push_front(1);
    int l=t;
    for(int i=2;i<=n;i++)
    {
        while(!q.empty() && q.front()<=(i-l))
        {
            q.pop_front();
        }
        while(!q.empty() && c[i]<=(c[q.back()]+s*(i-q.back()))) q.pop_back();
        q.push_back(i);
        m[i]=c[q.front()]+s*(i-q.front());
    }
    for(int i=1;i<=n;i++)
    {
        sol=sol+1LL*v[i]*m[i];
    }
    printf("%lld\n",sol);
    return 0;
}