Pagini recente » Cod sursa (job #1567164) | Cod sursa (job #667069) | Profil M@2Te4i | Monitorul de evaluare | Cod sursa (job #766843)
Cod sursa(job #766843)
#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;
long long 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,"%lld\n",sum);
fclose(f);
fclose(g);
}