Cod sursa(job #3224446)

Utilizator aeru1Ianos Alex-Marian aeru1 Data 15 aprilie 2024 13:32:24
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

#define TITLE "branza"
#define ll long long

ifstream f (TITLE".in");
ofstream g (TITLE".out");

int c[100010],p[100010];

int solve()
{
    int n,s,t;
    f>>n>>s>>t;
    for(int i=1; i<=n; i++)
        f>>c[i]>>p[i];
    deque<int>DQ;
    ll answer=0;
    for(int i=1; i<=n; i++)
    {
        for(;!DQ.empty() && c[i]<=c[DQ.back()]+s*(i-DQ.back()); DQ.pop_back());
        DQ.push_back(i);
        if(DQ.front()<i-t)
            DQ.pop_front();
        answer+=p[i]*(c[DQ.front()]+s*(i-DQ.front()));
    }
    g<<answer;
    return 0;
}

int main()
{
    solve();
    return 0;
}