Cod sursa(job #68443)

Utilizator floringh06Florin Ghesu floringh06 Data 27 iunie 2007 23:48:16
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
using namespace std;

#define MAX_N 100005
#define ll long long 

#include <stdio.h>

typedef struct 
 {
   int c;
   int p;
 } data;
 
FILE *fin=fopen("branza.in","r"),
     *fout=fopen("branza.out","w");
 
int n,s,t,i,li,lf;
data a[MAX_N];
int m[MAX_N]; 
int deq[MAX_N];
ll sol;
 
void includ(int i)
{
  int j,vl;
  deq[lf++]=i;
  j=lf-1;
  vl=a[j+1].c+(n-j-1)*s;
  while (j>li && vl<=a[j].c+(n-j)*s)
   { deq[j-1]=deq[j]; j--; }
  while (i-deq[li]>t) li++;
}  
   
void solve (void)
{
  int i;
  for (i=1; i<=n; i++)
   {
     includ(i);
     m[i]=a[deq[li]].c+(n-deq[li])*s-(n-i)*s;   
   }  
  for (i=1; i<=n; i++)
   sol+=m[i]*a[i].p;
  fprintf(fout,"%lld",sol); 
}    

int main()
{
   fscanf(fin,"%d %d %d",&n,&s,&t);
   for (i=1; i<=n; i++)
    fscanf(fin,"%d %d",&a[i].c,&a[i].p);       
   
   solve();
   fclose(fin);
   fclose(fout);
   
   return 0;
}