Cod sursa(job #2074255)
Utilizator | Mihail Turcan mihailraz | Data | 24 noiembrie 2017 12:26:39 |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fi("deque.in");
ofstream fo("deque.out");
int n,k,s;
int X[5000005];
deque <int> D;
int main()
{
fi>>n>>k;
for(int i=1; i<=n; i++)
{
fi>>X[i];
while(!D.empty() && X[i]<=X[D.back()])
D.pop_back();
D.push_back(i);
if(D.front()==i-k)
D.pop_front();
if(i>=k)
s+=X[D.front()];
}
fo<<s;
fi.close();
fo.close();
return 0;
}