Cod sursa(job #1306811)

Utilizator dorinmoldovanMoldovan Dorin dorinmoldovan Data 31 decembrie 2014 15:42:25
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include "stdio.h"
#include "stdlib.h"
#include <list>
using namespace std;

#define DIM 5000010

FILE *f, *g;

char sir[DIM];
int s[DIM];

int n, k, j, x, maximum, position;

std::list<int> int_list;

int main()
{
	f = fopen("secventa.in", "r");
	g = fopen("secventa.out", "w");

	// STEP 1: read the input data
	// read n
	fscanf(f, "%d", &n);
	// read k
	fscanf(f, "%d\n", &k);
	// read the string which contains the numbers
	fgets(sir, DIM, f);
	// insert the numbers from the string inside an array of integers
	j = 1;
	for(int i = 0; sir[i] != 0; i++)
	{
		int semn = 1;
		if(sir[i] == '-')
		{
			semn = -1;
			i++;
		}
		while(sir[i] >= '0' && sir[i] <= '9')
		{
			s[j] = s[j] * 10 + (sir[i] - '0');
			i++;
		}
		s[j] = s[j] * semn;
		j++;
	}

	// STEP 2: determine output data

	maximum = -30001;

	for(int i = 1; i <= n; i++)
	{
		while(!int_list.empty() && s[i] <= s[int_list.back()])
		{
			int_list.pop_back();
		}
		int_list.push_back(i);

		x = int_list.front();
		if((i - int_list.front()) >= k)
			int_list.pop_front();

		if(i >= k && s[int_list.front()] > maximum)
		{
			maximum = s[int_list.front()];
			position = i;
		}
	}

	fprintf(g, "%d %d %d", position - k + 1, position, maximum);

	fclose(f);
	fclose(g);

	return 0;
}