Cod sursa(job #68401)

Utilizator floringh06Florin Ghesu floringh06 Data 27 iunie 2007 19:20:45
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 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;

void arrange(int p)
{
  while (p>0 && b[deq[p]]<b[deq[p-1]])
   { deq[p-1]=deq[p]; p--; }
}

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=0; 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-k>0) arrange(i-k+1);
    if (i-deq[li]>=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;
}