Cod sursa(job #1933473)

Utilizator herbertoHerbert Mohanu herberto Data 20 martie 2017 18:56:23
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<stdio.h>
using namespace std;
#define MAXN 100001

long long cant[MAXN], dpoz[MAXN], dpret[MAXN], pret[MAXN], poz[MAXN];
int main(){
  FILE*fin=fopen("branza.in", "r");
  FILE*fout=fopen("branza.out", "w");
  int n, s, t, i, dr, st;
  long long sum;
  fscanf(fin, "%d%d%d", &n, &s, &t); t++;
  st=1; dr=0; sum=0;
  for(i=1; i<=n; i++){
    fscanf(fin, "%d%d", &pret[i], &cant[i]);
    if(i>=t && dpoz[st]==i-t)
      st++;
    while(dr>=st && pret[i]<dpret[dr]+(i-dpoz[dr])*s)
      dr--;
    dr++;
    dpret[dr]=pret[i]; dpoz[dr]=i;
    sum=sum+(dpret[st]+(i-dpoz[st])*s)*cant[i];
//    printf("%lld\n", sum);
  }
  fprintf(fout, "%lld", sum);
  return 0;
}