Cod sursa(job #766843)

Utilizator iris88Nagy Aliz iris88 Data 12 iulie 2012 12:32:12
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#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);
}