Pagini recente » Cod sursa (job #1918304) | Cod sursa (job #2249387) | Cod sursa (job #74707) | Cod sursa (job #2533786) | Cod sursa (job #1803356)
#include <iostream>
#include <cstdio>
using namespace std;
int n,k;
long long int s;
int a[5000001];
class Deque
{
private:
int inc,sf;
long long int arr[50000001];
public:
Deque()
{
inc=sf=0;
}
void adauga_inceput(int x)
{
for(int i=sf;i>=inc;i--)
arr[i+1]=arr[i];
sf++;
arr[inc]=x;
}
void adauga_sfarsit(int x)
{
arr[sf]=x;
sf++;
}
int prim()
{
return arr[inc];
}
int ultim()
{
return arr[sf-1];
}
void scoate_prim()
{
inc++;
}
void scoate_ultim()
{
sf--;
}
bool vida()
{
return sf-inc==0;
}
};
Deque d;
void solve()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<k ;i++)
{
while(!d.vida() && a[d.ultim()]>=a[i])
d.scoate_ultim();
d.adauga_sfarsit(i);
}
for(int i=k;i<=n;i++)
{
if(!d.vida() && d.prim()<=i-k)
d.scoate_prim();
while(!d.vida() && a[d.ultim()]>=a[i])
d.scoate_ultim();
d.adauga_sfarsit(i);
s+=a[d.prim()];
}
printf("%lld",s);
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
solve();
return 0;
}