Cod sursa(job #1379886)
| Utilizator | Data | 6 martie 2015 20:02:05 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.63 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int N, K;
int V[5000005];
int sum;
deque<int> DQ;
int main()
{
fin >> N >> K;
for (int i = 1; i <= N; ++i)
fin >> V[i];
for (int i = 1, x; i <= N; ++i)
{
while (!DQ.empty() && V[DQ.back()] >= V[i])
DQ.pop_back();
DQ.push_back(i);
while (DQ.front() <= i - K)
DQ.pop_front();
if (i >= K)
sum += V[DQ.front()];
}
fout << sum << '\n';
fin.close();
fout.close();
return 0;
}
