Cod sursa(job #262983)
Utilizator | Vicol Sergiu Constantin Ergo | Data | 19 februarie 2009 20:09:10 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
#define NMAX 5000100
int DQ[NMAX], A[NMAX], N, K, St, Dr;
long long Sum;
int main()
{
int i;
fin >>N >>K;
St = 1;
for (i = 1; i <= N; i++)
{
fin >>A[i];
A[i] += 10000000;
for (; A[i] <= A[DQ[Dr]] && Dr >= St; Dr--);
DQ[++Dr] = i;
if (DQ[St] <= i - K) St++;
if (i >= K)
Sum += (A[DQ[St]] - 10000000);
}
fout <<Sum;
fout.close();
return 0;
}