Cod sursa(job #2517068)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 2 ianuarie 2020 20:27:42
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 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];
        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;
}