Cod sursa(job #1182584)

Utilizator xtreme77Patrick Sava xtreme77 Data 6 mai 2014 20:55:06
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <deque>
#include <vector>
#define MAX 100014
using namespace std;
deque <int> dubla;
vector <int> cost;
int main()
{
    int n,s,t,x,y,minim;long long sol=0;
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);cost.push_back(sol);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        cost.push_back(x);
        while(!dubla.empty() and cost[i]<cost[dubla.back()]+s*(i-dubla.back()))
            dubla.pop_back();
        if(!dubla.empty() and dubla.front()<i-t)dubla.pop_front();
        dubla.push_back(i);
        sol+=(long long)(1LL*cost[dubla.front()]*y+1LL*s*(i-dubla.front())*y);
    }

    printf("%lld\n",sol);
    return 0;
}