Cod sursa(job #129980)

Utilizator marinMari n marin Data 30 ianuarie 2008 19:42:43
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DIM 262144
int st[1001];
int poz[1001];
int p, u;

char sir[DIM];

void add(int& v, int& pozitie){
  while(st[u] >= v && p < u){
    --u;
  }
  if(st[u] >= v){
    st[u] = v;
  }
  else{
    st[++u] = v;
  }
  poz[u] = pozitie;
}

void print(){
  for(int i=p;i<=u;++i)
    printf("(%d / %d) ", st[i], poz[i]);
  printf("\n");
}

int main(){
  FILE* f = fopen("secventa.in", "r");
  FILE* g = fopen("secventa.out", "w");
  int n, k;
  fscanf(f, "%d %d\n", &n, &k);

  int max = -31000;
  int str = -1;
  p = 0;
  u = 0;
  st[0] = 310000;
	
  int ind, x;

  x = 0;
  ind = 0;
  int  neg = 0;
  int i = 0;
  while(fgets(sir, DIM, f) != NULL)	{
    for(; sir[ind] != '\0'; ++ind) {
      if(sir[ind] >= '0' && sir[ind] <= '9')
	x = x*10+(sir[ind]-'0');
      else{
	if(sir[ind] == '-')
	  neg = 1;
	else{
	  if(neg)
	    x *= -1;
	    add(x, i);
            if(i>=k-1){
		while(i-poz[p] > k-1)
                  ++p;
		  if(st[p] > max){
		    max = st[p];
		    str = i-(k-1);
		  }
	    }
	   x = 0;
	   neg = 0;
	   ++i;
	}
      }
    }
    ind = 0;
  }

  fclose(f);
  fprintf(g, "%d %d %d\n", str+1, str+1+k-1, max);
  fclose(g);
  return 0;
}