Cod sursa(job #2057241)
Utilizator | Data | 4 noiembrie 2017 15:00:45 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <fstream>
using namespace std;
ifstream cin("deque.in") ;
ofstream cout ("deque.out") ;
int d[5000001] , v[5000001] ;
int main()
{
int n , k ;
cin >> n >> k ;
long long sum = 0 ;
int st = 0 , dr = -1 ;
for (int i = 0 ; i < n ; i++) {
cin >> v[i] ;
if ( st <= dr && d[st] == i - k ) {
st++ ;
}
while ( st <= dr && v[i] <= v[d[dr]]) {
dr-- ;
}
d[++dr] = i ;
if ( i >= k - 1) {
sum+= v[d[st]] ;
}
}
cout << sum ;
return 0;
}