Cod sursa(job #399724)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 20 februarie 2010 23:03:43
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out"); int arb[1000009],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 sumc,sumc2,pozitie=1,pozitie2=1,x,k,aux;
int main()
{         in>>n>>k;
        for(int i=1;i<=n;i++)
         {in>>x;update(i,x);}
         sumc=query(k);
        
         for(int i=k;i<=n;i++)
         {aux=query(i);
          if(aux>=sumc) {sumc=aux;pozitie=i;}}
        sumc2=-(1<<30)+1;
          int ax=sumc;
          for(int i=pozitie-k;i>=1;i--)
         {aux=ax-query(i-1);  
          if(aux>sumc2) {sumc2=aux;pozitie2=i;}}
          long long rez=sumc;
          if(sumc2!=-(1<<30)+1) rez=rez-sumc2;
          out<<pozitie2<<' '<<pozitie<<' '<<rez<<'\n';


      return 0;
}