Cod sursa(job #3239703)

Utilizator nicushor21Pirlog Marian Nicolae nicushor21 Data 7 august 2024 13:10:04
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long n,s,t,pret,i;
struct sap{
    long long p,c;
}v[100001];
deque <sap> brz;
int main()
{
    fin>>n>>s>>t;
    for(i=1;i<=n;i++)
        fin>>v[i].p>>v[i].c;
    pret = v[1].c * v[1].p;
    brz.push_back({v[1].p,1});
    for(i=2;i<=n;i++){
        while(!brz.empty() && i - brz.front().c > t)
            brz.pop_front();
        while(!brz.empty() && v[i].c * v[i].p <= v[i].c * (brz.front().p + (i - brz.front().c) * s))
            brz.pop_front();

        if(!brz.empty())
            pret += v[i].c * (brz.front().p + (i - brz.front().c) * s);
        else
            pret += v[i].c * v[i].p;

        brz.push_back({v[i].p,i});
    }
    fout<<pret;
    return 0;
}