Cod sursa(job #4562)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 5 ianuarie 2007 14:28:45
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
/*
  (C) Nemesis
  Infoarena secventa 2
 */

#include<stdio.h>
#define MAXN 50001
int a[MAXN], kmin[MAXN], n, k, maxi, maxj;
int sum[MAXN], min[MAXN], max;

/*
void afis()
{
  for(int i=1; i<=n; ++i) printf("%d) suma=%d min=%d kmin=%d\n",i,sum[i],min[i],kmin[i]);
} 
*/

void solve()
{
  sum[1]= a[1];
  min[1]= a[1];
  kmin[1]= 1;
  max= a[1];
  maxi=0;
  maxj=1;
  for(int i=2; i<=n; ++i) {
    sum[i]= sum[i-1] + a[i];
    if( sum[i] - min[i-k] > max) { max=sum[i]- min[i-k]; maxi=kmin[i-k]; maxj=i; }
    else if( sum[i] -min[i-k] == max && maxj-maxi > kmin[i-k]-i) { max=sum[i]-min[i-k]; maxi=kmin[i-k];maxj=i; }
    if(sum[i] > max) { max=sum[i]; maxi=0; maxj=i; };
    if( sum[i] < min[i-1]) { min[i]= sum[i]; kmin[i]=i; }
    else { min[i]= min[i-1]; kmin[i]=kmin[i-1]; }   
  }
}

int main()
{
  freopen("secv2.in","r",stdin);
  scanf("%d %d",&n,&k);
  for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
  solve();
  freopen("secv2.out","w",stdout);
  //afis();
  //printf("K=%d",k);
  printf("%d %d %d\n",maxi+1,maxj,max);
}