Cod sursa(job #370390)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 30 noiembrie 2009 23:09:12
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include<values.h>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out"); int arb[500009],n;
void update(int nod,int val)
{int pos=nod;
while(pos<=n)
{arb[pos]+=val;
pos+=((pos^(pos-1))&pos);
}}
int query(int dr)
{ if(dr==0) return 0;
int sum=0,loc=dr;
while(0<loc)
{sum+=arb[loc];
 loc-=(loc^(loc-1)&loc);
}

return sum;}


int main()
{       int sumc,sumc2,pozitie,pozitie2,x,k,aux;   in>>n>>k;
        for(int i=1;i<=n;i++)
         {in>>x;update(i,x);}
         sumc=query(k);
         for(int i=k+1;i<=n;i++)
         {aux=query(i);
          if(aux>sumc) {sumc=aux;pozitie=i;}}
         sumc2=-2500001;
          for(int i=pozitie-k;i>=1;i--)
         {aux=query(pozitie)-query(i-1);
          if(aux>sumc2) {sumc2=aux;pozitie2=i;}}
          out<<pozitie2<<' '<<pozitie<<' '<<sumc2<<'\n';


      return 0;
}