Cod sursa(job #1671739)
Utilizator | Data | 2 aprilie 2016 09:41:28 | |
---|---|---|---|
Problema | Deque | Scor | 5 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream fi("deque.in");
ofstream fo("deque.out");
deque <int> D;
int a[5000001];
int n,k,poz,x,i;
long long sol;
int main()
{
fi>>n>>k;
for(i=1;i<=n;i++) fi>>a[i];
while (poz<=n)
{poz++;
while ( ! D.empty() and D.front() + k <= poz ) D.pop_front();
while ( ! D.empty() and a[D.front()] > a[poz] ) D.pop_front();
D.push_back(poz);
if (poz>=k) sol+=a[D.front()];
//fo << a[D.front()]<<" ";
}
fo<<sol;
return 0;
}