Cod sursa(job #164505)

Utilizator pandaemonAndrei Popescu pandaemon Data 24 martie 2008 12:48:21
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#include<iostream.h>
#define LMAX 100001

long n,s,t,i;  /// n saptamani // interval maxim de t saptamani // cost stocare
long c[LMAX],p[LMAX];
long long m[LMAX],v[LMAX],min,ind,total;

long long check(int x)
{ long minim=v[x-t]; ind=x-t;

    for(long i=x-t+1;i<x;i++)
     if(v[i]<=minim) {minim=v[i]; ind=i;}

  return minim; }


main()
{ freopen("branza.in","r",stdin);
  freopen("branza.out","w",stdout);

  scanf("%ld %ld %ld",&n,&s,&t);

  for(i=1;i<=n;i++) { scanf("%ld %ld",&c[i],&p[i]);
		      v[i]=c[i]+(n-i)*s; }

  min=m[1]=v[1]; total=min-s*(n-1);

  for(i=2;i<=n;i++)  {

   if( i-t>1 && ind==(i-t-1) ) min=check(i);

   if(v[i]<=min) {min=v[i]; ind=i;}

   m[i]= ( ( min-(n-ind)*s ) + s*(i-ind) ) * p[i];

   total+=m[i];	     }


printf("%lld\n",total);  }