Cod sursa(job #2123652)

Utilizator patcasrarespatcas rares danut patcasrares Data 6 februarie 2018 14:42:39
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
#include<iostream>
#include<deque>
#define DN 100005
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,c,p;
long long rez;
deque<pair<int,int> >d;
int main()
{
    fin>>n>>s>>t;
    for(int i=1;i<=n;i++)
    {
        fin>>c>>p;
        while(1)
        {
            if(d.empty())
                break;
            if(d.back().y+(i-d.back().x)*s<c)
                break;
            d.pop_back();
        }
        d.pb({i,c});
        while(1)
        {
            if(d.empty())
                break;
            if(d.front().x>=i-t)
                break;
            d.pop_front();
        }
        rez+=1LL*(d.front().y+1LL*(i-d.front().x)*s)*p;
    }
    fout<<rez;
}