Cod sursa(job #2313230)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 6 ianuarie 2019 13:58:23
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <fstream>
#include <deque>
#define NM 100001
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long n,s,t,v[NM],p,sm,i;
deque < long long > dq;
int main()
{
    f>>n>>s>>t;
    for(i=1;i<=n;i++){ f>>v[i]>>p;
       if(i-t-1==dq.front()) dq.pop_front();
       while(!dq.empty()&&v[i]<=v[dq.back()]+s*(i-dq.back())) dq.pop_back();
       dq.push_back(i);
       sm+=(p*v[dq.front()]+s*(i-dq.front())*p);
    }
    g<<sm<<'\n';
    return 0;
}