Cod sursa(job #771244)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 25 iulie 2012 12:23:12
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<string.h>
#include<deque>

#define MAXL 10000005

using namespace std;

deque < pair <int, int> > A;

int n, k, x, y, res = -30001;
char S[ MAXL ];

int main()
{
	FILE *f = fopen("secventa.in", "r");
	
	int i, j = 0, val, ok;
	
	fscanf(f, "%d %d", &n, &k);
	fgets(S, 3, f);
	fgets(S, 10000000, f);
	
	fclose(f);
	
	for(i = 1; i < k; i++)
	{
		val = 0, ok = 1;
		
		while(S[j] == ' ')
			j++;
		if(S[j] == '-')
			ok = -1, j++;
		while(S[j] >= '0' && S[j] <= '9')
			val = val * 10 + S[j] - '0', j++;
		val *= ok;
		
		while(!A.empty() && val <= A.front().first)
			A.pop_front();
		A.push_front(make_pair(val, i));
		
	}
	
	for( ; i <= n; i++)			
	{
		val = 0, ok = 1;
		
		while(S[j] == ' ')
			j++;
		if(S[j] == '-')
			ok = -1, j++;
		while(S[j] >= '0' && S[j] <= '9')
			val = val * 10 + S[j] - '0', j++;
		val *= ok;
		
		while(!A.empty() && val <= A.front().first)
			A.pop_front();
		A.push_front(make_pair(val, i));
		
		if(A.back().second == i - k)
			A.pop_back();
		
		if(A.back().first > res)
			res = A.back().first, y = i;
	}
	
	x = y - k + 1;
	
	FILE *g = fopen("secventa.out", "w");
	
	fprintf(g, "%d %d %d\n", x, y, res);
	
	fclose(g);

	return 0;
}