Cod sursa(job #3247816)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 9 octombrie 2024 11:04:07
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <queue>
#define int long long
using namespace std;

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

const int Nmax = 1e5 + 5;

pair<int, int> v[Nmax];//cost, cantitate
deque<int> d;

signed main()
{
    int n, t, s, i;
    int ans = 0;
    cin >> n >> s >> t;
    for(i = 1; i <= n; i ++)
        cin >> v[i].first >> v[i].second;
    for(i = 1; i <= n; i ++)
    {
        while (!d.empty() && v[i].first <= v[d.back()].first + s * (i - d.back()))
            d.pop_back();
        while (!d.empty() && i - d.front() > t)
            d.pop_front();
        int ans1 = 1e18;
        if(!d.empty())
            ans1 = v[i].second * (v[d.front()].first + s * (i - d.front()));
        int ans2 = v[i].first * v[i].second;
        ans += min(ans1, ans2);
     //   cout << i << " " << min(ans1, ans2) << "  ";
       // if(!d.empty())
         //   cout << d.back();
     //   cout << '\n';
        d.push_back(i);
    }
    cout << ans;
    return 0;
}