Cod sursa(job #1806455)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 15 noiembrie 2016 12:50:14
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
int n,s,t,m[maxN],v[maxN],c[maxN],l;
deque<int> q;
long long sol;
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]=1;
    q.push_front(1);
    l=t;
    for(int i=2;i<=n;i++)
    {
        while(!q.empty() && q.front()<=(i-l)) q.pop_front();
        while(!q.empty() && (m[q.back()]+s*(i-q.back()))>=m[i]) q.pop_back();
        q.push_back(i);
        m[i]=m[q.front()]+s*(i-q.front());
    }
    for(int i=1;i<=n;i++)
    {
        sol=sol+1LL*m[i]*v[i];
    }
    printf("%lld\n",sol);
    return 0;
}