Pagini recente » Cod sursa (job #2882259) | Cod sursa (job #1081429) | Cod sursa (job #2289275) | Cod sursa (job #502151) | Cod sursa (job #48495)
Cod sursa(job #48495)
#include <stdio.h>
#define NM 50002
FILE *fin, *fout;
long a[NM];
struct nr{ long x,j;};
nr sum[NM],b[NM];
void sort(long l, long r)
{long m=(l+r)>>1,k,j,i;
if (l==r) return ;
sort(l,m);
sort(m+1,r);
for (i=l,j=m+1,k=l;i<=m||j<=r;)
if (j>r||(i<=m&&sum[i].x<sum[j].x))
b[k++]=sum[i++];
else b[k++]=sum[j++];
for (k=l;k<=r;k++) sum[k]=b[k];
}
int main()
{long i,n,k,s=0,max,smax,smin,ok,im;
fin=fopen("secv2.in","rt");
fout=fopen("secv2.out","wt");
fscanf (fin,"%ld %ld\n",&n,&k);
for (i=1;i<=n;i++)
{
fscanf(fin,"%ld",&a[i]);
s+=a[i];
sum[i].x=s;
sum[i].j=i;
}
smax=sum[k].x;
sort (1,n);
ok=1;
i=1;
s=n;
while (ok)
{
im=sum[i].j-sum[s].j;
if (sum[s].x>=0) smin=sum[s].x-sum[i].x;
else smin=sum[s].x+sum[i].x;
if (im<0) im*=-1;
if (smin>smax&&im>=k)
{smax=smin;
ok=0;
}
else if (im<k&&smin>smax)
{
if (sum[s-1].x-sum[i].x>sum[s].x-sum[i+1].x)
s--;
else i++;
}
else ok=0;
}
if (sum[s].j>sum[i].j)
fprintf(fout,"%ld %ld %ld",sum[i].j+1,sum[s].j,smax);
else
fprintf(fout,"%ld %ld %ld",sum[s].j,sum[i].j,smax);
return 0;
}