Cod sursa(job #2388706)

Utilizator adiaioanaAdia R. adiaioana Data 26 martie 2019 12:46:34
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <deque>
#define N 100100
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
int n,s,t,b[N],c[N],sc[N];
unsigned long long sum;
struct chestie{
int ind,m;
}ch;
deque <chestie> mom;
int main()
{
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++)
        cin>>b[i]>>c[i],sc[i]=sc[i-1]+c[i];

    for(int i=1;i<=n;i++)
    {
        while(!mom.empty() && (mom.back().ind+t<i ||mom.back().m+s*(i-mom.back().ind)>=b[i]))
              mom.pop_back();
        mom.push_back({i,b[i]});
        while(!mom.empty() && mom.front().ind+t<i)
            mom.pop_front();

        ch=mom.front();
        sum=sum+(ch.m+s*(i-ch.ind))*c[i];
    }

    cout<<sum<<'\n';
    return 0;
}