Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 128 | Cod sursa (job #2880770) | Cod sursa (job #2112468) | Cod sursa (job #332348) | Cod sursa (job #1861768)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k;
int i;
struct a{
int poz;
int val;
}x;
struct b{
long long poz;
long long val;
};
deque <a>q;
int main()
{
f >> n >> k;
for(i = 1 ; i <= k ; ++i){
f >> x.val;
x.poz = i;
while(!q.empty() && q.back().val > x.val)
q.pop_back();
q.push_back(x);
}
b smin;
smin.val = q.front().val;
smin.poz = q.front().poz;
int capats = 1;
int capatd = k;
for(i = k + 1 ; i <= n ; ++i){
f >> x.val;x.poz = i;
capats++;
capatd++;
if(q.front().poz < capats)q.pop_front();
while(!q.empty() && q.back().val > x.val)
q.pop_back();
q.push_back(x);
smin.val += q.front().val;
}
g << smin.val;
return 0;
}