Cod sursa(job #1147176)

Utilizator zaharia_horiaZaharia Horia zaharia_horia Data 19 martie 2014 17:18:43
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
using namespace std;
int i;
struct branza
{
    int z;
    long long c;
};
branza dq[100100];
int st=1,dr=0,t,n;
long long cant,cost,s;
long long total;
void stanga()
{
    if(i-dq[st].z>t)
        st++;
}
void dreapta()
{
    while((long long)dq[dr].c*cant+(i-dq[dr].z)*s*cant>(long long)cost*cant&&dr>=st)
    {
        dr--;
    }
    dq[++dr].c=cost;
    dq[dr].z=i;
}
int main()
{
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    fin>> n>> s>> t;
    for(i=1;i<=n;i++)
    {
        stanga();
        fin>>cost >>cant;
        dreapta();
        total+=(long long)dq[st].c*cant;
        if(dq[st].z<i)
            total+=(long long)s*cant*(i-dq[st].z);
    }
    fout<< total;
    return 0;
}