Cod sursa(job #1477607)
| Utilizator | Data | 26 august 2015 16:31:52 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.56 kb |
#include <cstdio>
#include <vector>
#include <deque>
#define f first
#define s second
using namespace std;
deque < pair <int, int> > D;
int N, K, X; long long S;
int main(){
freopen("deque.in" , "r", stdin );
freopen("deque.out", "w", stdout);
scanf("%d %d", &N, &K);
for(int i = 1; i <= N; i ++){
scanf("%d", &X);
while(!D.empty() && D.back().s >= X)
D.pop_back();
D.push_back( make_pair(i, X) );
if(i - D.front().f == K)
D.pop_front();
if(i >= K)
S += D.front().s;
}
printf("%lld", S);
fclose(stdin );
fclose(stdout);
return 0;
}
