Cod sursa(job #562638)
Utilizator | Data | 23 martie 2011 16:59:31 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include<fstream>
#include<deque>
#include<vector>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k,c,a,e,ok;
long long s;
deque<int> d;
vector<int> v;
deque<int>::iterator it,o;
int main()
{ int i;
f>>n>>k;
v.reserve(5000001);
for(i=0;i<n;i++)
{ f>>a;
while(!d.empty()&&v[d.back()]>=a) d.pop_back();
d.push_back(i);
v.push_back(a);
if(d.front()==i-k) d.pop_front();
if(i>k-2) s+=v[d.front()];
}
g<<s<<'\n';
f.close(); g.close();
return 0;
}