Cod sursa(job #166151)

Utilizator alecmanAchim Ioan Alexandru alecman Data 27 martie 2008 15:17:38
Problema Secventa 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>

#define INPUT "secv2.in"
#define OUTPUT "secv2.out"
#define INFI -2000000000
#define NMAX 50001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N, K;
long a[ NMAX ], sum[ NMAX ];

void readValues();

void solveFunction();

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}

void readValues()
{
  fscanf(fin, "%ld %ld", &N, &K);

  for(long i = 1; i <= N; ++i)
  {
    fscanf(fin, "%ld", &a[ i ]);

    if(i <= K)
      sum[ i ] = sum[ i - 1] + a[ i ];
    else
      sum[ i ] = sum[ i - 1 ] + a[ i ] - a[ i - K ];
  }
}

void solveFunction()
{
  long SMax, PIMax, PFMax, SNou, MaxMin, PMm;

  SMax = sum[ K ];
  PIMax = 1;
  PFMax = K;

  for(long i = K + 1; i <= N; ++i)
  {
    if( a[ i ] < 0)
    {
      SNou = 0;
      MaxMin = INFI;
      PMm = -1;

      while( i <= N && a[ i ] < 0)
      {
	SNou += a[ i ];
	
	if(sum[ i ] > MaxMin)
	{
          MaxMin = sum[ i ];
	  PMm = i;
	}

	++i;
      }

      if(i <= N)
      {
	if(SMax + SNou + a[ i ]< sum[ i ])
	{
          SMax = sum[ i ];
	  PIMax = i - K + 1;
	  PFMax = i;
	}
	else
	{
          SMax += SNou;
	  SMax += a[ i ];
	  PFMax = i;
	}
      }
      else
      {
	if(MaxMin > SMax)
	{
          SMax = MaxMin;
	  PIMax = PMm - K + 1;
	  PFMax = PMm;
	}
      }
    }
    else
    {
      if(SMax + a[ i ] < sum[ i ])
      {
	SMax = sum[ i ];
	PIMax = i - K + 1;
	PFMax = i;
      }
      else
      {
	SMax += a[ i ];
	PFMax = i;
      }
    }
  }

  fprintf(fout, "%ld %ld %ld\n", PIMax, PFMax, SMax);
}