Cod sursa(job #2057021)

Utilizator CryshanaGanea Carina Cryshana Data 4 noiembrie 2017 14:12:24
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <fstream>
using namespace std;

const long long N=100000;
long long c[N],p[N],d[N];

int main()
{
    ifstream fin ("branza.in");
    ofstream fout ("branza.out");
    long long st=0, dr=-1, n, t, s, j, mem;
    long long C=0;
    fin>>n>>s>>t;
    for(int i=0; i<n; i++)
    {
        fin>>p[i]>>c[i];
        if(st<=dr&&d[st]==i-t)
            st++;
        while(st<=dr&&p[d[dr]]>=p[i])
            dr--;
        d[++dr]=i;
        mem=c[i]*s*(i-d[st])+c[i]*p[d[st]];
        for(j=st; j<i; j++)
        {
            if(c[i]*s*(i-d[j])+c[i]*p[d[j]]<mem)
                mem=c[i]*s*(i-d[j])+c[i]*p[d[j]];
        }
        if(mem<p[i]*c[i])
            C+=mem;
        else C+=p[i]*c[i];
        cout<<C;
    }
    fout<<C;
    return 0;
}