Cod sursa(job #68384)

Utilizator floringh06Florin Ghesu floringh06 Data 27 iunie 2007 18:59:15
Problema Secventa 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
//using namespace std;

#define MAX_N 50005

#include <stdio.h>

FILE *fin=fopen("secv2.in","r"),
     *fout=fopen("secv2.out","w");
    
int b[MAX_N];
int deq[MAX_N];
int i,lf,li,in,out,max;    
int n,k,x;
     
int main()
{
  fscanf(fin,"%d %d",&n,&k);
  for (i=1; i<=n; i++) {
   fscanf(fin,"%d",&x);
   b[i]=b[i-1]+x;
  }
  li=1; lf=1;
  max=-1000000;
  if (k==n)
   {
    fprintf(fout,"1 %d %d",n,b[n]);
    return 0;
   }
  for (i=1; i<=n; i++)
   {
    deq[lf++]=i;
    if (i-deq[li+1]>=k && b[deq[li+1]]<b[deq[li]])
      li++;
    if (i-deq[li]+1>=k)
    if (b[i]-b[deq[li]]>max)
     {
       max=b[i]-b[deq[li]];
       in=deq[li]+1;
       out=i;
     }
   }
   fprintf(fout,"%d %d %d",in,out,max);
  
 fclose(fin);
 fclose(fout);
 
 return 0;
}