Cod sursa(job #164518)

Utilizator pandaemonAndrei Popescu pandaemon Data 24 martie 2008 12:57:22
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<iostream.h>
#define LMAX 100009

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

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

    for(long 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("%lld %lld %lld",&n,&s,&t);

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

  min=m[1]=v[1]; total=(min-s*(n-1))*p[1]; ind=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);  }