Cod sursa(job #166103)

Utilizator stefanrStefan Ruseti stefanr Data 27 martie 2008 14:04:36
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<fstream.h>
ifstream fin("secv2.in");
ofstream fout("secv2.out");

int v[50001],n,d[50001],p[50001],k;

int main()
{fin>>n>>k;
long s=0,max,q;
int i;
for(i=1;i<=n;i++) fin>>v[i];
for(i=n;i>n-k;i--) s+=v[i];
d[n-k+1]=s;
p[n-k+1]=k;
max=s;
q=n-k+1;
for(i=n-k;i>=1;i--)
 {s-=v[i+k];
  if(s>d[i+1])
   {d[i]=s+v[i];
    p[i]=k;
   }
  else
   {d[i]=d[i+1]+v[i];
    p[i]=p[i+1]+1;
   }
  s+=v[i];
  if(d[i]>max)
   {max=d[i];
    q=i;
   }
 }
fout<<max<<" "<<q<<" "<<q+p[q]-1<<"\n";
fin.close();
fout.close();
return 0;
}