Cod sursa(job #2635836)
| Utilizator | Data | 15 iulie 2020 17:47:34 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
//#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int NMAX = 5000005;
int v[NMAX], deck[NMAX], k, n, fr, bk;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
int i;
long long s=0;
fin >> n >> k;
for(i = 1; i <= n; i++){
fin >> v[i];
}
bk = 0; fr = 1;
for(i = 1; i <= n; i++){
while(v[i] <= v[ deck[bk] ] && fr <= bk)
bk--;
deck[++bk] = i;
if(deck[fr] == i - k)
fr++;
if(i >= k)
s += v[ deck[fr] ];
}
fout << s;
return 0;
}
