Cod sursa(job #915407)

Utilizator FayedStratulat Alexandru Fayed Data 14 martie 2013 23:32:52
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#include <deque>
#define NMAX 100001
using namespace std;

int n;
long long int S,Smax,T,C[NMAX],P[NMAX];
deque < int >Deque;

int main(){

    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%lld%lld",&n,&S,&T);
    for(register int i=1;i<=n;++i){

        scanf("%lld%lld",&C[i],&P[i]);
        while(!Deque.empty() && C[i] < C[Deque.back()] + S*(i-Deque.back()))
            Deque.pop_back();
            Deque.push_back(i);

        while(!Deque.empty() && Deque.front()+T < i)
            Deque.pop_front();
         Smax+=C[Deque.front()]*P[i] + P[i]*S*(i-Deque.front());
    }
printf("%lld",Smax);

return 0;
}