Cod sursa(job #942561)

Utilizator superman_01Avramescu Cristian superman_01 Data 22 aprilie 2013 22:45:05
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<deque>

#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))

FILE *f=fopen("branza.in","r");
FILE *g=fopen("branza.out","w");

using namespace std;

const int NMAX=100005;

struct branza {
LL cant;
LL cost;
};
branza v[NMAX];
LL time,extra,n;
LL bst[NMAX];
deque <int> q;

void Read ( void )
{
    fscanf(f,"%lld%lld%lld",&n,&extra,&time);
    for(int i(1) ; i <= n ; ++i )
    {
        fscanf(f,"%lld%lld",&v[i].cost,&v[i].cant);
    }
    fclose(f);
}
void Solve ( void )
{
    bst[1]=v[1].cant*v[1].cost;
    q.push_back(1);
    for(int i(2) ; i <= n ; ++i )
    {
        for ( ;!q.empty() && q.front() < i - time ; q.pop_front() );

        for( ; !q.empty() && ( v[i].cost < ( v[q.back()].cost + extra*(i-q.back()) ) ); q.pop_back()  );
       q.push_back(i);

      bst[i]=1LL*(v[q.front()].cost+extra*(i-q.front()))*v[i].cant;
    }
}
void Write ( void )
{
    LL Answer(0);
    for(int i(1) ; i <= n ; ++i )
        Answer+=bst[i];
    fprintf(g,"%lld",Answer);
    fclose(g);
}

int main ( void )
{
    Read();
    Solve();
    Write();
    return 0;
}