Pagini recente » Cod sursa (job #1989830) | Cod sursa (job #1061963) | Cod sursa (job #725609) | Cod sursa (job #3203794) | Cod sursa (job #1779482)
#include<cstdio>
#include<deque>
using namespace std;
#define DEBUG false
#define DBG if(DEBUG)
int main() {
FILE *fin = fopen("deque.in", "r"),
*fout = fopen("deque.out", "w");
long long n, k, suma = 0;
fscanf(fin, "%d%d", &n, &k);
deque<int> nr, poz;
for(int i=1; i<=n; i++) {
int x;
fscanf(fin, "%d", &x);
while(!nr.empty() && nr.back() > x) {
DBG printf("%d > %d\n", nr.back(), x);
nr.pop_back(), poz.pop_back();
}
nr.push_back(x);
poz.push_back(i);
DBG printf("nr %d %d %d %d %d\n", nr[0], nr[1], nr[2], nr[3], nr[4]);
DBG printf("poz %d %d %d %d %d\n", poz[0], poz[1], poz[2], poz[3], poz[4]);
if(i>=k) { // daca nu e inca in construire prima secventa
while(poz.back() - poz.front() >= k)
nr.pop_front(), poz.pop_front();
suma += nr.front();
}
}
fprintf(fout, "%d\n", suma);
return 0;
}