Pagini recente » Cod sursa (job #13394) | Cod sursa (job #698783) | Cod sursa (job #3293292) | Cod sursa (job #2715093) | Cod sursa (job #343716)
Cod sursa(job #343716)
//la ce te uiti....
using namespace std;
#include <cstdio>
#include <deque>
deque <int> D;
int n, k, i, v[5000010];
long long sol;
int main(){
freopen("deque.in", "r",stdin);
freopen("deque.out", "w",stdout);
scanf("%d %d %d", &n, &k,&v[1]);
D.push_back(1);
for (i = 2; i <= n; i++)
{scanf("%d", &v[i]);
while( !D.empty() && D.front() <= i - k ) D.pop_front();
while( !D.empty() && v[i] <= v[ D.back() ] ) D.pop_back();
D.push_back(i);
if(i >= k)
sol+= (long long)v[ D.front() ];
}
printf("%lld", sol);
return 0;
}