Cod sursa(job #333929)

Utilizator mlazariLazari Mihai mlazari Data 24 iulie 2009 17:47:16
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include<stdio.h>

#define NMAX 100003

long long rez;
int n,s,t,i,fd=1,ld=0;
long long c[NMAX],p[NMAX],deque[NMAX];

int main() {
  freopen("branza.in","r",stdin);
  scanf("%d %d %d",&n,&s,&t);
  for(i=0;i<n;i++) {
    scanf("%lld %lld",c+i,p+i);
    while((ld>=fd)&&(c[deque[ld]]+s*(i-deque[ld])>=c[i])) ld--;
    deque[++ld]=i;
    if(deque[fd]<i-t) fd++;
    rez+=(c[deque[fd]]+s*(i-deque[fd]))*p[i];
  }
  freopen("branza.out","w",stdout);
  printf("%lld",rez);
  return 0;
}