Cod sursa(job #2883236)

Utilizator KataIsache Catalina Kata Data 1 aprilie 2022 12:32:27
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fin ("branza.in");
ofstream fout("branza.out");

int v[100005], cantitate[100005];
deque<int> q;

int main()
{
    int i,x,n,s,t;
    long long int total;
    fin>>n>>s>>t;
    for(i=1; i<=n;i++)
        fin>>v[i]>>cantitate[i];
    total=v[1]*cantitate[1];
    q.push_front(1);
    for(i=2;i<=n;i++)
    {
        while(i-q.front()>t)
            q.pop_front();
        while(!q.empty() && (s*(i-q.back())+v[q.back()])>= v[i])
            q.pop_back();
        q.push_back(i);
        total+=1ll*cantitate[i]*((i-q.front())*s+v[q.front()]);
    }
    fout<<total;
    return 0;
}