Cod sursa(job #1809211)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 18 noiembrie 2016 18:33:53
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
FILE *f=fopen("branza.in","r");
FILE *f1=fopen("branza.out","w");
long long c[100010],p[100010],n,s,t;
long long sum;
deque <long> q;
void citire( )
{
    fscanf(f,"%d%d%d",&n,&s,&t);
    for(int i=1;i<=n;i++)
      fscanf(f,"%d%d",&c[i],&p[i]);

}
int good(int j,int i)
{
    if(((i-j)*s+c[j])*p[i]<c[i]*p[i])
       return 0;
    return 1;
}
void add(int i)
{
   while(!q.empty()&&good(q.back(),i)==1)
         q.pop_back();
    q.push_back(i);
}
void eraser(int i)
{
     while(!q.empty()&&(i-q.front()+1>t))
          q.pop_front();
}
void rez( )
{
    q.push_back(1);
    sum=c[1]*p[1];
    for(int i=2;i<=n;i++)
    {
        add(i);
        eraser(i);
        int j=q.front();
        sum+=((i-j)*s+c[j])*p[i];

    }
}
int main()
{
    citire();
    rez( );
    fprintf(f1,"%lld",sum);
    return 0;
}