Cod sursa(job #164950)

Utilizator alecmanAchim Ioan Alexandru alecman Data 24 martie 2008 23:14:15
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>

#define INPUT "secv2.in"
#define OUTPUT "secv2.out"
#define NMAX 50001

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

long N, K, PIMax, PFMax, pozPoz, sumNeg;
long a[ NMAX ], sum[ NMAX ], SMax[ NMAX ], PMax[ NMAX];

void readValues();

void solveFunction();

void printSolution();

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 - K] + a[ i ];
  }
}

void solveFunction()
{
  long pozPoz;

  SMax[ K ] = sum[ K ];
  PMax[ K ] = 1;
  sumNeg = 0;
  pozPoz = K;

  for(long i = K+1; i <= N; ++i)
  {
    if(a[ i ] > 0)
    {
      if(SMax[ pozPoz ] + a[ i ] +sumNeg > sum[ i ])
      {
	SMax[ i ] = SMax[ pozPoz] + a[ i ] + sumNeg;
	PMax[ i ] = PMax[ pozPoz];
      }
      else
      {
	SMax[ i ] = sum[ i ];
	PMax[ i ] = i - K + 1;
      }

      pozPoz = i;
    }
    else
    {
      if(SMax[ i - 1] + a[ i ] < sum[ i ])
      {
	SMax[ i ] = sum[ i ];
	PMax[ i ] = i - K + 1;
      }
      else
	sumNeg += a[ i ];
    }
  }

  printSolution();
}

void printSolution()
{
  long long VMax = SMax[ K ];
  long pozitie, poz2;

  for(long i = K + 1; i <= N; ++i)
    if(VMax < SMax[ i ])
    {
      VMax = SMax[ i ];
      pozitie = PMax[ i ];
      poz2 = i;
    }
  fprintf(fout, "%ld %ld %lld\n", pozitie, poz2, VMax);
}