Cod sursa(job #2274393)

Utilizator Iorgus08Iorgus Serghei Cicala Iorgus08 Data 1 noiembrie 2018 19:10:36
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <fstream>

using namespace std;

const int N=100000;

int d[N],v[N],n,k;

ifstream in("branza.in");

ofstream out("branza.out");

int main()

{

    long long n,i,k,s=0,p,t,sum=0;
    in>>n>>s>>t;
    k=t+1;
    int st=0,dr=-1;
    for(i=0;i<n;i++)

    {

      in>>v[i];

      in>>p;

      if(d[st]==i-k)

      {

        st++;

      }

      while(st<=dr&&v[i]<=(v[d[dr]]+(i-d[dr])*s))

      {

        dr--;

      }

      d[++dr]=i;
          sum+=p*(v[d[st]]+(i-d[st])*s);

    }

    out<<sum;

    return 0;

}