Cod sursa(job #38282)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 25 martie 2007 16:58:22
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream.h>

int main()
{
 long p[5001],sk[5001], maxk[5001];
 long i,k,n,s,max,pc,ps,pf;

 ifstream fin("secv2.in");
 fin>>n>>k;
 for(i=1;i<=n;i++) fin>>p[i];
 fin.close();

 s=0;		//se calculeaza in s profitul obtinut prin alegerea primelor k chioscuri
 for(i=1;i<=k;i++)
  s=s+p[i];

 sk[k]=maxk[k]=max=s; //evident, sk[k]=maxk[k]=s, iar ps=1 si pf=k
 ps=1;pf=k;
 pc=1;		     //varibila pc retine pozitia de inceput a secventei curente  	
 for (i=k+1;i<=n;i++)
 {
  sk[i]=sk[i-1]+p[i]-p[i-k]; //se calculeaza si se actualizeaza valorile celor 2 vectori
  if(maxk[i-1]+p[i]>sk[i])
   maxk[i]=maxk[i-1]+p[i];
  else
  {
   maxk[i]=sk[i];
   pc=i-k+1;
  }
  if (maxk[i]>max)  //se actualizeaza, daca este necesar, valoarea maxima a profitului
  {
   max=maxk[i];
   ps=pc;
   pf=i;
  }
 }

 ofstream fout("secv2.out");
 fout<<ps<<" "<<pf<<" "<<max;
 fout.close();

 return 0;
}