Cod sursa(job #770391)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 22 iulie 2012 20:56:46
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");

int n,k,i,v[50001],deque[50001];
long maxim, sum;
int xi,xf;
int beg,end,trace,nt;

/*void afisare()
{for(int j=beg; j<=end; j++)
    g<<v[deque[j]]<<" ";
 g<<"    Sum:    "<<sum<<"   Trace:"<<trace<<"      Maximum:"<<maxim;
 g<<endl;}   */

int main()
{
f>>n>>k;
maxim=-5000001;    
for(i=1; i<=n; i++)
  f>>v[i];

beg=1;  end=0;  sum=0;  trace=0;  nt=0;
for(i=1; i<=n; i++)
 {end++;
  deque[end]=i;
  sum=sum+v[i];
   
  if((end-beg)>k-1)
     {trace=trace+v[deque[beg]+nt];
      nt++;} 
         
         
  while((end-beg)>=k && trace<=0) 
       {sum=sum-v[deque[beg]]; 
        trace=trace-v[deque[beg]]; 
        beg++; 
        nt--;}           
  //afisare(); 
  if(i>=k && sum>maxim)
    {maxim=sum;  xi=beg;  xf=end;}
  }              
     
g<<xi<<" "<<xf<<" "<<maxim;       
f.close();
g.close();    
return 0;}