Cod sursa(job #942560)

Utilizator superman_01Avramescu Cristian superman_01 Data 22 aprilie 2013 22:43:34
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 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 {
int cant;
int 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,"%d%d",&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*min(v[i].cost,(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;
}