Cod sursa(job #1233466)
Utilizator | Savu 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;
}