Pagini recente » Cod sursa (job #1987441) | Cod sursa (job #1994086) | Cod sursa (job #2376432) | Cod sursa (job #3188368) | Cod sursa (job #3159408)
//https://infoarena.ro/problema/deque
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
int main()
{
int n,i,x,k;
long long sum=0;
deque <pair<int,int>> dq;
fin>>n>>k;
fin>>x;
dq.emplace_back(0,x);
for(i=1;i<n;i++)
{
fin>>x;
if(dq.empty()==0)
{
while((dq.empty()==false)&&(x<dq.back().second))
{
dq.pop_back();
}
}
dq.emplace_back(i,x);
if(i>=(k-1))
{
while((dq.empty()==false)&&(dq.front().first<=(i-k)))
{
dq.pop_front();
}
//cout<<dq.front().second<<"\n";
if(dq.empty()==0)
{
sum+=(long long)dq.front().second;
}
}
}
// cout<<dq.front().second<<"\n";
// sum+=(long long)dq.front().second;
//return 0;
// for(auto &x : dq)
// {
// cout<<x.first<<" "<<x.second<<"\n";
// }
fout<<sum;
return 0;
}