Cod sursa(job #1539563)
Utilizator | Data | 30 noiembrie 2015 23:51:56 | |
---|---|---|---|
Problema | Deque | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
deque <int> d;
int i, n, k, a[10001]; long long sol=0;
int main()
{
in>>n>>k;
for(i=1;i<=n;i++)
in>>a[i];
for(i=1;i<=n;i++)
{
while(!d.empty() && a[i]<a[d.back()])
d.pop_back();
d.push_back(i);
if(d.front()==i-k)
d.pop_front();
if(i>=k) sol+= a[d.front()];
}
out<<sol;
return 0;
}