Pagini recente » Cod sursa (job #2170990) | Cod sursa (job #1297353) | Cod sursa (job #773724) | Profil Dobricean_Ioan | Cod sursa (job #1804071)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
struct str
{
long long val;
long long poz;
};
deque <str>d;
int n,k,S,i;
str x,prim,cap1,cap2;
int main()
{
f>>n>>k;
for(i=1;i<=k;i++){
f>>x.val;
x.poz=i;
if(i>1)
prim=d.back();
while(prim.val>x.val && !d.empty())
{
d.pop_back();
prim=d.back();
}
d.push_back(x);
}
for(i=k+1; i<=n; i++)
{
f>>x.val;
x.poz=i;
prim=d.back();
cap1=d.front();
S+=cap1.val;
while(prim.val>x.val && !d.empty())
{
d.pop_back();
prim=d.back();
}
d.push_back(x);
cap1=d.front();
cap2=d.back();
if(cap2.poz-cap1.poz>=k)
d.pop_front();
}
prim=d.front();
S+=prim.val;
g<<S;
return 0;
}