Cod sursa(job #56599)

Utilizator RazvanSSavu Razvan RazvanS Data 30 aprilie 2007 00:15:09
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>

#define MAX 50001

#define MAXBUF 400000

char buffer[MAXBUF];
int V[MAX];
int p;

void sub(int &x)
    {x=0;
     int k=1;
     while(buffer[p]==' ' || buffer[p]=='\n') p++;
     if(buffer[p]=='-') {p++, k=-1;} 
     for( ; buffer[p]>='0' && buffer[p]<='9' ; p++)
             x = x*10 + buffer[p] - '0';
     x*=k;    
    }         
    
    
int main( void )
     {
      int n, k, c1, c2, s, smax=0, si, sa;
      freopen("secv2.in", "r", stdin);
      fread(buffer, 1, MAXBUF, stdin);
      sub(n);
      sub(k);
      int i;
      for(i=1;i<=n;++i)
          sub(V[i]);
      
      for(i=1;i<=k;++i)
         smax+=V[i];
      
      s=0;
      c1=1;
      c2=k;
      si=smax;
      for(i=k+1;i<=n;++i)
          {s+=V[i-k];
           if(s<=0) {
                     sa=si-s+V[i];
                     s=0;
                     if(sa>smax) {smax=sa; c1=i-k+1; c2=i;}
                    }
              else {
                    sa=si+V[i];
                    if(sa>smax) {smax=sa; c2=i;}
                   }
           si=sa;
          }
      
      freopen("secv2.out", "w", stdout);
      printf("%d %d %d\n", c1, c2, smax);
      
      return 0;
      }