Cod sursa(job #1233466)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 25 septembrie 2014 15:35:50
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <cstdio>
using namespace std;
FILE *f=fopen ("deque.in","r");
FILE *g=fopen ("deque.out","w");

int b[5000010],a[5000010],n,ma;
long long sum=0;
void Solve()
{
    int k=0,ls=0,i;
    int j=0;
    for (i=1;i<=n;i++)
    {

    while (k>0 && a[i]<a[b[k]] && k>=j) k--;
    k++;
    b[k]=i;
    while (b[j]<i-ma+1 && j<=k) j++;
    if (i-ma+1>=1) {sum+=a[b[j]];}


    }



}


int main()
{
    int i;
fscanf(f,"%d %d",&n,&ma);
for (i=1;i<=n;i++)
{
    fscanf (f,"%d",&a[i]);
}
Solve();
fprintf (g,"%lld",sum);


    return 0;
}