Cod sursa(job #157765)

Utilizator alecmanAchim Ioan Alexandru alecman Data 13 martie 2008 11:30:59
Problema Secventa 2 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<stdio.h>
#include<math.h>

#define INPUT "secv2.in"
#define OUTPUT "secv2.out"
#define NMax 50002
#define INFI -200000000

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

long n, k;
long poz[ NMax ], sum[ NMax ];

void readValues();

void quick(long, long);

void solveFunction();

void printSolution(long, long, long);

int main()
{
  readValues();

  quick( 1, n);

  solveFunction();

  fclose(fin);
  fclose(fout);
  
  return 0;
}

void readValues()
{
  long val;

  fscanf(fin, "%ld %ld", &n, &k);

  for(long i = 1; i <= n; ++i)
  {
    fscanf(fin, "%ld", &val);
    sum[ i ] = sum[ i - 1 ] + val;
    poz[ i ] = i;
  }

}

void quick(long st, long dr)
{
  long l = st, m = dr;

  while( l != m)
  {
    if(( l < m && sum[ l ] > sum[ m ]) || ( l > m && sum[ l ] < sum[ m ]))
    {
      sum[ l ] = sum[ l ] + sum[ m ];
      sum[ m ] = sum[ l ] - sum[ m ];
      sum[ l ] = sum[ l ] - sum[ m ];
      poz[ l ] = poz[ l ] + poz[ m ];
      poz[ m ] = poz[ l ] - poz[ m ];
      poz[ l ] = poz[ l ] - poz[ m ];
      l = l + m;
      m = l - m;
      l = l - m;

      if ( l < m )
	      --m;
      else
	      ++m;
    }

    else
    {
      if( l < m)
        --m;

      else
	++m;
    }
  }

  if( l != st) quick( st, l - 1);
  
  if( l != dr) quick( l + 1, dr);
}

void solveFunction()
{
  int l = 1;

  long maxim = INFI, start = 0, stop = 0;

  for( long i = n; i > sqrt( n ) && l; --i)
  {
    for(long j = 1; j <= n && l; ++j)
    {
      if (poz[ i ] - poz[ j ] >= k)
      {
	if( maxim < sum[ i ] - sum [ j ])
	{
          maxim = sum[ i ] - sum[ j ];
	  start = poz[ j ];
	  stop = poz[ i ];
	}
      }
    }
  }

  printSolution(start, stop, maxim);  
}

void printSolution(long start, long stop, long value)
{
  fprintf(fout, "%ld %ld %ld\n", start + 1, stop, value);
}