Cod sursa(job #203434)

Utilizator drag0shSandulescu Dragos drag0sh Data 16 august 2008 14:26:25
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>

#define MAX 50005

FILE *f,*g;
long n,k;
long int v[MAX];
long s[MAX],miny[MAX],maxy[MAX];

long min(long a,long b){
  if(s[a]<s[b])return a;
  return b;
}

long max(long a,long b){
  if(s[a]<s[b])return b;
  return a;
}
 
void citire(){
  long i;
  fscanf(f,"%ld %ld",&n,&k);
  for(i=1;i<=n;i++)fscanf(f,"%ld",&v[i]);
}



int main(){
  f=fopen("secv2.in","r");
  g=fopen("secv2.out","w");
  
  long i;
  citire();

  for(i=1;i<=n;i++)s[i]=s[i-1]+v[i];
  miny[1]=1;
  maxy[n]=n;
  for(i=2;i<=n;i++){ 
    miny[i]=min(miny[i-1],i);
    maxy[n-i+1]=max(n-i+1,maxy[n-i+2]);
  }
  long d1,d2,dif;
  d1=1;
  d2=maxy[k];
  dif=s[maxy[k]];
  for(i=2;i<=n-k+1;i++) 
    if(   s[maxy[i+k-1]]-s[miny[i-1]]>dif){
      dif=s[maxy[i+k-1]]-s[miny[i-1]];
      d1=miny[i-1]+1;
      d2=maxy[i+k-1];
  
  }
  fprintf(g,"%ld %ld %ld",d1,d2,dif);

  fclose(f);
  fclose(g);
  return 0;
}