Cod sursa(job #2305809)
Utilizator | Data | 21 decembrie 2018 09:17:35 | |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.63 kb |
#include <iostream>
#include <fstream>
#define size 5000000
using namespace std;
int v[size], dq[size];
int main () {
ifstream fin ("deque.in");
ofstream fout ("deque.out");
int n, k, st, dr, s;
fin>>n>>k;
st = 0; dr = -1; s = 0;
for ( int i = 0; i < n; i++ ) {
fin>>v[i];
//scot din st
if ( st <= dr && dq[st] == i - k )
st++;
//scot din dr
while ( st <= dr && v[i] <= v[dq[dr]] )
dr--;
//adaug i
dq[++dr] = i;
//actualizez rez global
if ( i >= k - 1 )
s += v[dq[st]];
}
fout<<s;
return 0;
}