Cod sursa(job #333928)
| Utilizator | Data | 24 iulie 2009 17:45:21 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.48 kb |
#include<stdio.h>
#define NMAX 100003
long long rez;
int n,s,t,i,fd=1,ld=0;
int 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("%d %d",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;
}
