Cod sursa(job #2798956)
| Utilizator | Data | 12 noiembrie 2021 09:56:55 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
#include <deque>
#define MAXN 5000000
using namespace std;
ifstream fin( "deque.in" );
ofstream fout( "deque.out" );
deque <int> d;
int v[MAXN + 1];
int main(){
int n, k, i, s;
fin >> n >> k;
s = 0;
for( i = 0; i < n; i++ ){
fin >> v[i];
if( !d.empty() && d.front() == i - k )
d.pop_front();
while( !d.empty() && v[d.back()] >= v[i] )
d.pop_back();
d.push_back(i);
if( i >= k - 1 )
s += v[d.front()];
}
fout << s;
return 0;
}
