Cod sursa(job #2042761)
Utilizator | Teodor Marchitan Teodor.m | Data | 19 octombrie 2017 01:20:11 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <bits/stdc++.h>
using namespace std;
const int NMax = 5 * 1e6 + 5;
int A[NMax];
long long int sum;
int main()
{
ifstream fin("deque.in");
ofstream fout("deque.out");
int N, K;
fin >> N >> K;
deque <int> d;
for(int i = 1; i <= N; ++i) {
fin >> A[i];
}
for(int i = 1; i <= N; ++i) {
while (!d.empty() and A[d.back()] > A[i]) {
d.pop_back();
}
d.push_back(i);
if(d.front() == i - K) {
d.pop_front();
}
if(i >= K) {
sum += A[d.front()];
}
}
fout << sum;
return 0;
}