Pagini recente » Rating John Dalska (raroleoe) | Cod sursa (job #399724)
Cod sursa(job #399724)
#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;
}