Cod sursa(job #131742)

Utilizator floringh06Florin Ghesu floringh06 Data 4 februarie 2008 13:34:44
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
using namespace std;  
   
#define MAX_N 50005  
#include <cstdio>  
   
 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);  
     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;  
 }