Cod sursa(job #2884898)

Utilizator matei123Biciusca Matei matei123 Data 5 aprilie 2022 10:08:47
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("branza.in"); ofstream g("branza.out");
const long long MAX_N = 100000;
struct Index
{   long long val,index; };
long long n,s,t,c[1 + MAX_N],p[1 + MAX_N];
deque<Index> dq;
long long back_cost(long long i)
{   return 1LL * p[i + 1] * (dq.back().val + (i + 1 - dq.back().index) * s); }
int main()
{   f>>n>>s>>t;
    for (long long i = 1; i <= n; i++) f>>c[i]>>p[i];
    long long ans;
    ans = 1LL * p[1] * c[1];
    dq.push_back({c[1], 1});
    for (long long i = 2; i <= n; i++)
    {   ans += min(1LL * p[i] * c[i], 1LL * p[i] * (dq.front().val + (i - dq.front().index) * s));
        if (i < n)
        {   long long iCost = 1LL * p[i + 1] * (c[i] + s);
            while (dq.size() > 0 && iCost <= back_cost(i)) dq.pop_back();
            dq.push_back({c[i], i});
            while (i - dq.front().index + 1 > t) dq.pop_front();
        }
    }
    g<<ans;
    return 0;
}