Pagini recente » Cod sursa (job #307272) | Cod sursa (job #2461922) | Cod sursa (job #238505) | Cod sursa (job #2763118) | Cod sursa (job #3182479)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque <pair<long long int,long long int> > d;
long long int n,k,sum,a;
void deque1(long long int a,long long int poz);
void deque2(long long int a,long long int poz);
int main()
{
fin>>n>>k;
for(long long int i=1;i<=n;i++)
{
fin>>a;
if(i<k)
deque1(a,i);
else
if(i==k)
{
deque1(a,i);
sum+=d.front().first;
}
else
{
deque2(a,i);
}
}
fout<<sum;
return 0;
}
void deque1(long long int a,long long int poz)
{
while(d.size() && a<d.back().first)
{
d.pop_back();
}
d.push_back({a,poz});
}
void deque2(long long int a,long long int poz)
{
if(d.front().second<poz-k+1)
d.pop_front();
while(d.size() && a<d.back().first)
{
d.pop_back();
}
d.push_back({a,poz});
sum+=d.front().first;
}