Cod sursa(job #205839)

Utilizator mordredSimionescu Andrei mordred Data 3 septembrie 2008 02:06:28
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>
#define nmax 50001
#define inf (1<<30)
int a[nmax],n,k;
int s[nmax],min[nmax],start,end,max,i;

int main(){
 freopen("secv2.in","r",stdin);
 freopen("secv2.out","w",stdout);
 
 scanf("%d %d",&n,&k);
 
 for(i=1;i<=n;++i)
    scanf("%d", &a[i]),
    s[i] = s[i-1] + a[i];
  
 min[1] = 1;
 for(i=2;i<=n;++i)
    if(s[min[i-1]] > s[i])
        min[i] = i;
    else
        min[i] = min[i-1];
 
 max = s[k]; start = 1; end = k;
 
 for(i=k+1; i<=n; ++i)
    if(s[i] - s[min[i-k]] > max){
        max = s[i] - s[min[i-k]];
        start = min[i-k] + 1;
        end = i;
        }
 
 if(start == 2 && a[1] > 0)
    start = 1,
    max += a[1];
   
 printf("%d %d %d",start,end,max);
 return 0;    
}