Pagini recente » Cod sursa (job #150757) | Cod sursa (job #494587)
Cod sursa(job #494587)
#include <fstream>
#include <deque>
using namespace std;
const char InFile[]="deque.in";
const char OutFile[]="deque.out";
ifstream fin(InFile);
ofstream fout(OutFile);
struct s
{
s(int x2=0, int pos2=0):x(x2),pos(pos2){}
int x,pos;
};
int n,k,x,sol;
deque<s> d;
int main()
{
fin>>n>>k;
for(register int i=1;i<=k;++i)
{
fin>>x;
while(!d.empty())
{
if(d.back().x<x)
{
break;
}
d.pop_back();
}
d.push_back(s(x,i));
}
sol+=d.front().x;
for(register int i=k+1;i<=n;++i)
{
fin>>x;
while(!d.empty())
{
if(d.back().x<x)
{
break;
}
d.pop_back();
}
d.push_back(s(x,i));
while(d.front().pos<=i-k)
{
d.pop_front();
}
sol+=d.front().x;
}
fin.close();
fout<<sol;
fout.close();
return 0;
}