Cod sursa(job #1980489)

Utilizator nnnmmmcioltan alex nnnmmm Data 13 mai 2017 11:05:45
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <algorithm>
#include <deque>

struct saptamana
{
 long long cerere,pret;
};

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

saptamana v[NMAX];

std::deque<long long> dcoada;

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

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

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

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