Pagini recente » Cod sursa (job #1582130) | Cod sursa (job #423895) | Cod sursa (job #756929) | Cod sursa (job #1314629) | Cod sursa (job #1981877)
#include <cstdio>
#include <deque>
using namespace std;
struct salam
{
int val,pos;
};
deque <salam> D;
int main()
{
freopen ("deque.in","r",stdin);
freopen ("deque.out","w",stdout);
int n,k,i,x;
long long S=0;
salam a;
scanf ("%d %d",&n,&k);
for (i=1; i<k; i++)
{
scanf ("%d",&x);
while (!D.empty()&&x<=D.front().val)
{
D.pop_front();
}
a.val=x;
a.pos=i;
D.push_front(a);
}
for (i=k; i<=n; i++)
{
scanf ("%d",&x);
while (!D.empty()&&x<=D.front().val)
{
D.pop_front();
}
if (D.size()<=k)
{
a.val=x;
a.pos=i;
D.push_front(a);
}
if (i-D.back().pos>=k)
{
D.pop_back();
}
S+=D.back().val;
}
printf ("%lld\n",S);
return 0;
}