Pagini recente » Cod sursa (job #706680) | Cod sursa (job #944656) | Cod sursa (job #1522944) | Cod sursa (job #1248569) | Cod sursa (job #465031)
Cod sursa(job #465031)
#include <fstream>
#include <deque>
#define NMAX 5000005
using namespace std;
long n,k,sum;
struct elm
{
long val;
long poz;
};
int main()
{
fstream fin,fout;
fin.open("deque.in",ios::in);
fout.open("deque.out",ios::out);
deque<elm*> coada;
fin>>n>>k;
for(long i=1;i<=n;i++)
{
elm *e= new elm;
fin>>e->val;
e->poz=i;
while(!coada.empty() && coada.back()->val >= e->val)
{
elm *c=coada.back();
delete c;
coada.pop_back();
}
coada.push_back(e);
if(i>=k)
{
elm *c = coada.front();
while(i-c->poz>=k)
{
c=coada.front();
delete c;
coada.pop_front();
c=coada.front();
}
sum+=c->val;
}
}
fout<<sum<<'\n';
fin.close();
fout.close();
return 0;
}