Cod sursa(job #2056953)

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

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

int main()
{
    ifstream fin ("branza.in");
    ofstream fout ("branza.out");
    int 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;
            if(p[i]*c[i]<c[i]*s*(i-d[st])+c[i]*p[d[st]])
                   C+=p[i]*c[i];
                else {
                        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]];
                }
                        C+=mem;
                }
    }
    fout<<C;
return 0;
}