Cod sursa(job #2615831)

Utilizator As932Stanciu Andreea As932 Data 15 mai 2020 17:38:48
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <deque>

using namespace std;

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

typedef long long ll;

ll n,s,t,ans;
struct week
{
    ll c,p,poz;
}w;
deque <week> d;

int main()
{
    cin>>n>>s>>t>>w.c>>w.p;

    d.push_back({w.c,w.p,1});

    ans=1LL*w.c*w.p;

    for(int i=2;i<=n;i++)
    {
        cin>>w.c>>w.p;
        w.poz=i;

        while(!d.empty() && i-d.front().poz>t)
            d.pop_front();

        while(!d.empty() && w.c<=1LL*(i-d.back().poz)*s+d.back().c)
            d.pop_back();

        d.push_back({w.c,w.p,i});

        ans+=(i-d.front().poz)*1LL*w.p*s+1LL*w.p*d.front().c;
    }

    cout<<ans;

    return 0;
}