Cod sursa(job #67627)

Utilizator floringh06Florin Ghesu floringh06 Data 25 iunie 2007 12:49:28
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 0.96 kb
using namespace std;

#define MAX_N 100005
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define ll long long

#include <stdio.h>
#include <fstream>

FILE *fin=fopen ("branza.in","r"),
     *fout=fopen ("branza.out","w");

typedef struct
 {
   int c;
   int p;
 } data;

data a[MAX_N];
int cost[MAX_N]; // cost[i] costul minim obtinut de taran in ziua i
int n,s,t;
ll sol=0;

void citire (void)
{
  int i;
  fscanf(fin,"%d %d %d",&n,&s,&t);
  for (i=1; i<=n; i++)
   fscanf(fin,"%d %d",&a[i].c,&a[i].p);
}

void solve (void)
{
 int i,j,k;
 cost[1]=a[1].c*a[1].p;
 for (i=2; i<=n; i++)
 {
  cost[i]=a[i].p*a[i].c;
  for (j=max(i-t,1); j<i; j++)
   {
     k=a[j].c*a[i].p+(i-j)*a[i].p*s;
     if (k<=cost[i])
	cost[i] = k;
   }
 }
 for (i=1; i<=n; i++)
    sol+=cost[i];
}

int main()
{
    citire();

    solve();

    fprintf(fout,"%lld\n",sol);

    fclose(fin);
    fclose(fout);

    return 0;
}