Pagini recente » Cod sursa (job #1229624) | Cod sursa (job #1047582) | Cod sursa (job #1547515) | Cod sursa (job #667073) | Cod sursa (job #766837)
Cod sursa(job #766837)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
int main()
{
FILE *f = fopen("deque.in","r");
FILE *g = fopen("deque.out","w+");
int n,k;
fscanf(f,"%d %d",&n,&k);
vector<int> sir;
sir.reserve(n);
deque<int> pozmin;
int sum = 0;
int x;
for (int i=0;i<k;i++)
{
fscanf(f,"%d",&x);
while (!pozmin.empty() && sir[pozmin.back()]>x)
pozmin.pop_back();
pozmin.push_back(i);
sir.push_back(x);
}
for (int i=k;i<n;i++)
{
int a = pozmin.front();
if (i-a>=k)
pozmin.pop_front();
sum+=sir[a];
fscanf(f,"%d",&x);
while (!pozmin.empty() && sir[pozmin.back()]>x)
pozmin.pop_back();
pozmin.push_back(i);
sir.push_back(x);
}
int a = pozmin.front();
sum+=sir[a];
fprintf(g,"%d\n",sum);
fclose(f);
fclose(g);
}