Cod sursa(job #2517067)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 2 ianuarie 2020 20:26:27
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <deque>
#define N 10000000

using namespace std;

deque <int> q;
long long c[N],b[N];

int main()
{
    ifstream f("branza.in");
    ofstream g("branza.out");
    long long n,s,t,ss=0;
    f>>n>>s>>t;
    for(int i=1;i<=n;++i)
    {
        f>>c[i]>>b[i];
        if(i==1)
        {
            q.push_back(i);
            ss=ss+(long long)c[i]*b[i];
        }
        else
        {
            while(!q.empty() && i-q.front()>t) q.pop_front();
            while(!q.empty() && (i-q.back())*s*b[i]+c[q.back()]*b[i]>c[i]*b[i]) q.pop_back();///am gasit un pret mai bun
            q.push_back(i);
            ss=ss+(i-q.front())*s*b[i]+c[q.front()]*b[i];
        }
    }
    g<<ss;
    f.close();
    g.close();
    return 0;
}