Cod sursa(job #1182583)

Utilizator xtreme77Patrick Sava xtreme77 Data 6 mai 2014 20:51:45
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 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();
        while(dubla.size()>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;
}