Cod sursa(job #1980474)

Utilizator nnnmmmcioltan alex nnnmmm Data 13 mai 2017 10:54:59
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>
#include <deque>

struct saptamana
{
 int cerere,pret;
};

const int NMAX=100001,INF=(1ll<<31)-1;

saptamana v[NMAX];

std::deque<int> dcoada;

void Adauga(int pos,int s)
{
 if(dcoada.empty())
    {
     dcoada.push_back(pos);
     return;
    }
 while(!dcoada.empty() && v[dcoada.front()].pret+(pos-dcoada.front())*s>v[pos].pret)
       {
        dcoada.pop_front();
       }
 dcoada.push_back(pos);
}

void Sterge(int pos,int t)
{
 while(!dcoada.empty() && dcoada.front()<=pos-t)
       dcoada.pop_front();
}

int main()
{
 FILE *in=fopen("branza.in","r");
 int n,s,t;
 fscanf(in,"%d %d %d ",&n,&s,&t);
 for(int i=1;i<=n;i++)
     {
      fscanf(in,"%d %d ",&v[i].pret,&v[i].cerere);
     }
 fclose(in);

 int rasp=0;
 for(int i=1;i<=n;i++)
     {
      Adauga(i,s);
      Sterge(i,t);
      int pret=v[dcoada.front()].pret+(i-dcoada.front())*s;
      rasp+=v[i].cerere*pret;
     }
 FILE *out=fopen("branza.out","w");
 fprintf(out,"%d\n",rasp);
 fclose(out);
 return 0;
}