Cod sursa(job #113580)

Utilizator mgntMarius B mgnt Data 10 decembrie 2007 20:44:17
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <cstdlib>
using namespace std;

int main()
{
  int const maxn = 50000;
  int const maxv = +25000;
  int const minv = - maxv;
  FILE * fin, * fout;
  int v[maxn], maxs[maxn], len[maxn], sum[maxn];
  int n, k, i, max, pos1, pos2;
  
  fin=fopen("secv2.in", "r");
  setvbuf(fin, NULL, _IOFBF, 100 * 1024);
  fscanf(fin, "%d %d", &n, &k);
  
  for(i=0;i+10<n;i+=10)
    fscanf(fin, "%d %d %d %d %d %d %d %d %d %d",
      &v[i+0], &v[i+1], &v[i+2], &v[i+3], &v[i+4],
      &v[i+5], &v[i+6], &v[i+7], &v[i+8], &v[i+9]);
  for(;i<n;i++)
    fscanf(fin, "%d", & v[i]);
  fclose(fin);

  sum[0]=v[0];
  for(i=1;i<n;i++)
    sum[i]=sum[-1+i]+v[i];
  for(i=-1+n;i>=-1+k;i--)
    sum[i]-=sum[i-k+1];
  
  maxs[0]=v[0];
  len [0]=1;
  for(i=1;i<n;i++)
    if(0<maxs[-1+i]) {
      maxs[i]=maxs[-1+i]+v[i];
      len [i]=1+len[-1+i];
    }
    else {
      maxs[i]=v[i];
      len [i]=1;
    }
  
  max=-1 + maxn*minv;
  for(i=-1+k;i<n;i++) {
    sum[i]+=maxs[i-k+1];
    if(sum[i]>max) {
      max =sum[i];
      pos1=1+(i-k+1)-len[i-k+1]+1;
      pos2=1+i;
    }
  }
  fout=fopen("secv2.out", "w");
  fprintf(fout, "%d %d %d\n", pos1, pos2, max);
  fclose(fin);
  return 0;
}