Cod sursa(job #264122)

Utilizator MciprianMMciprianM MciprianM Data 21 februarie 2009 15:09:45
Problema Secventa 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream>
using namespace std;
int a[50009];
int main(){
  int i, max=-10000, sum, n,x, i1, i2,r1,r2,k;
  ifstream f("secv2.in");
  f>>n>>k;
  for(i=1;i<=n;i++){
    f>>x;
    a[i]=a[i-1]+x;
  }
  f.close();
  for(i=1;i+k-1<=n;i++)
    if(max<(a[i+k-1]-a[i-1]))
      max=a[i+k-1]-a[i-1],r1=i,r2=i+k-1;
  sum=a[1];i1=1;i2=1;
  for(i=2;i<=n;i++){
   x=a[i]-a[i-1];
   if(sum+x>=0)  sum+=x, i2++;
   else sum=0,i1=i+1,i2=i;
   if(max<sum&&((i2-i1+1)>=k)){  max=sum;r1=i1,r2=i2;}
  }
  f.close();
  ofstream g("secv2.out");
  g<<r1<<' '<<r2<<' '<<max<<'\n';
  g.close();
  return 0;
}