Cod sursa(job #164921)

Utilizator alecmanAchim Ioan Alexandru alecman Data 24 martie 2008 22:43:14
Problema Secventa 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 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;
long a[ NMAX ], sum[ NMAX ];

long long SMax, sumNeg;

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()
{
  SMax = sum[ K ];
  PIMax = 1;
  PFMax = K;
  sumNeg = 0;
  pozPoz = -1;

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

  printSolution();
}

void printSolution()
{
  fprintf(fout, "%ld %ld %lld\n", PIMax, PFMax, SMax);
}