Cod sursa(job #3248640)

Utilizator ReBeGhElRebegea Stefan ReBeGhEl Data 12 octombrie 2024 13:29:38
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

vector < int > cost , v;
deque < int > dq;
int n,s,t;

void read()
{
    cin>>n>>s>>t;
    cost.resize(n+1);
    v.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>cost[i]>>v[i];
}

void solve()
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty() && dq.front()<i-t)
            dq.pop_front();
        while(!dq.empty() && cost[i]<cost[dq.back()]+s)
            dq.pop_back();
        dq.push_back(i);
        ans+=cost[dq.front()]*v[i]+(i-dq.front())*s*v[i];
    }
    cout<<ans;
}

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