Cod sursa(job #1182582)

Utilizator xtreme77Patrick Sava xtreme77 Data 6 mai 2014 20:49:46
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <deque>
#include <vector>
#define min(a,b) (((a)<(b))?(a):(b))
#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 and i-dubla.front()>t)dubla.pop_front();
        dubla.push_back(i);
        int fata=dubla.front();
        sol+=1LL*cost[dubla.front()]*y+1LL*s*(i-dubla.front())*y;
    }

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