Cod sursa(job #1252522)
Utilizator | Data | 30 octombrie 2014 20:53:40 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
#define Nmax 5000100
using namespace std;
int N, K, Left = 1, Right, A[Nmax], Deque[Nmax];
long long Sum;
int main() {
ifstream in("deque.in");
ofstream out("deque.out");
in >> N >> K;
for(int i = 1; i <= N; i++) {
in >> A[i];
while(Left <= Right && A[i] < A[Deque[Right]])
Right--;
Deque[++Right] = i;
if(Deque[Left] == i - K)
Left++;
if(i >= K)
Sum += A[Deque[Left]];
}
out << Sum << '\n';
in.close();
out.close();
return 0;
}