Cod sursa(job #770380)

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

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

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

int main()
{
f>>n>>k;
maxim=-50001;    
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++)
 {
  while((end-beg)>=k-1 && trace<=0) 
       {sum=sum-v[deque[beg]]; 
        trace=trace-v[deque[beg]]; 
        beg++; 
        nt--;}       
  end++;
  deque[end]=i;
  sum=sum+v[i];
  if((end-beg)>k-1)
     {trace=trace+v[deque[beg]+nt];
      nt++;} 
  if(i>=k && sum>maxim)
    {maxim=sum;  xi=beg;  xf=end;}
  }              
     
g<<xi<<" "<<xf<<" "<<maxim;       
f.close();
g.close();    
return 0;}