Cod sursa(job #3247799)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 9 octombrie 2024 10:11:52
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <queue>

using namespace std;
using ll = long long;

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

int s;
struct prio {
    ll ind, val;
    bool operator < (const prio & rhs) const {
        ll s1 = 0, s2 = 0; ///prio, rhs
        if(ind > rhs.ind)
            s2 += s * (ind - rhs.ind);
        else
            s1 += s * (rhs.ind - ind);
        return (s1 + val) > (s2 + rhs.val);
    }
};
priority_queue <prio> pq;

int main()
{
    int n, t;
    cin >> n >> s >> t;

    ll cost, cate, ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> cost >> cate;
        while(!pq.empty()) { ///stergem branza expirata
            prio now = pq.top();
            if(now.ind + t < i)
                pq.pop();
            else
                break;
        }
        pq.push({i, cost});
        prio now = pq.top();
        ans += 1LL * ((i - now.ind) * s + now.val) * cate;
        //cout << ((i - now.ind) * s + now.val) << '\n';
        //pq.push({i, cost});
    }
    /*while(!pq.empty()) {
        prio now = pq.top();
        pq.pop();
        cout << now.ind << " " << now.val << '\n';
    }*/
    cout << ans;
    return 0;
}