Pagini recente » clasament-teme | Cod sursa (job #998747) | Cod sursa (job #876584) | Cod sursa (job #2619896) | Cod sursa (job #2229675)
#include <fstream>
#include <deque>
using namespace std;
deque <int>D;
int v[5000005];
int main()
{ ifstream cin("deque.in");
ofstream cout("deque.out");
int n,k,s=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
D.push_back(1);
for(int i=2;i<=n;i++)
{
if(v[i]<=v[D.front()])
{
D.pop_front();
D.push_front(i);
}
else
{ while(1)
{
if(v[D.back()]>v[i])
{D.pop_back();}
else
{
D.push_back(i);
break;
}
}
}
if(i-D.front()<k&&k<=i)
{
s+=v[D.front()];
}
else
if(k<=i)
{ while(1)
{
if(i-D.front()>=k)
D.pop_front();
else
break;
}
s+=v[D.front()];
}
}
cout<<s;
return 0;
}