Cod sursa(job #1294268)

Utilizator rocandu16Badulescu Dan Andrei rocandu16 Data 17 decembrie 2014 10:20:53
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>

using namespace std;

#define MAX 5000000

long long sum=0;
int dq[MAX+1], top=0, bot=1;
int v[MAX+1];

int main()
{
    FILE *fin, *fout;

    fin = fopen ("deque.in","r");
    fout = fopen("deque.out","w");

    int n, k, i, x,cost,y;

    fscanf (fin, "%d%d%d", &n,&cost,&k);
    fscanf(fin, "%d%d", &v[1],&y);

    dq[++top]=1;

    for(i=2; i<=n; i++)
    {
        fscanf(fin, "%d%d", &v[i],&y);
       // if(v[dq[top]]>v[i])
        //{
            while(top >=bot && v[dq[top]]+(i-dq[top])*cost>v[i])
                top--;
            dq[++top]=i;
       // }
       // else
         //   dq[++top]=i;
        if(dq[bot] == i-k)
            bot++;

        if(i >= k)
            sum+=v[dq[bot]]*y+(i-dq[top])*cost;
    }

    fprintf(fout, "%lld", sum);
    return 0;
}