Cod sursa(job #2988688)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 5 martie 2023 12:30:48
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("branza.in");
ofstream out("branza.out");

#define int long long

int n,t,c[100005],p[100005],s;
deque<pair<int,int>>d;
int ans;

signed main()
{
    in >> n >> s >> t;
    for (int i = 1; i <= n; i++)
        in >> c[i] >> p[i];
    for (int i = 1; i <= n; i++)
    {
        while (!d.empty() and d.front().second + t < i)
            d.pop_front();
        while (!d.empty() and p[i] * d.back().first + p[i] * (i - d.back().second) * s >= p[i] * c[i])
            d.pop_back();
        d.push_back({c[i],i});
        //cout << d.front().second << ' ';
        ans += p[i] * d.front().first + p[i] * (i - d.front().second) * s;
    }
    out << ans;
    return 0;
}