Cod sursa(job #2049747)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 27 octombrie 2017 16:47:46
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <cstdio>
#define MAXN 100000
int v[MAXN],dq[MAXN];
int main()
{
    FILE *fin,*fout;
    fin=fopen("branza.in","r");
    fout=fopen("branza.out","w");
    int n,s,t,st,dr,p;
    long long cost=0;
    fscanf(fin,"%d%d%d",&n,&s,&t);
    st=0;dr=-1;
    for(int i=0;i<n;i++)
    {
        fscanf(fin,"%d%d",&v[i],&p);
        while(st<=dr && v[i]<v[dq[dr]]+(i-dq[dr])*s)
            dr--;
        dq[++dr]=i;
        if(dq[st]+t<i)
            st++;
        cost+=(long long)(v[dq[st]]+(i-dq[st])*s)*p;
    }
    fprintf(fout,"%lld",cost);
    fclose(fin);
    fclose(fout);
    return 0;
}