Pagini recente » Cod sursa (job #2611490) | Cod sursa (job #3148036) | Cod sursa (job #909470) | Cod sursa (job #3263841) | Cod sursa (job #48530)
Cod sursa(job #48530)
#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,ii,is;
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;
ii=0;
s=is=n;
while (ok&&i<s)
{
if (sum[s].j>sum[i].j) im=sum[s].j-sum[i].j;
else im=sum[i].j-sum[s].j;
if (sum[s].j>sum[i].j) smin=sum[s].x-sum[i].x;
else if (sum[s].j<sum[i].j) smin=sum[i].x-sum[s].x;
if (smin>smax&&im>=k)
{smax=smin;
ii=sum[s].j;
is=sum[i].j;
ok=0;
}
else if (im<k&&smin>smax)
{
if (sum[s].j>sum[i].j)
{
if (sum[s-1].x-sum[i].x>sum[s].x-sum[i+1].x)
s--;
else i++;
}
else if (sum[s].j<sum[i].j)
{
if (sum[i+1].x-sum[s].x>sum[i].x-sum[s-1].x)
i++;
else s--;
}
}
else ok=0;
}
if (is>ii)
fprintf(fout,"%ld %ld %ld",ii+1,is,smax);
else fprintf(fout,"%ld %ld %ld",is+1,ii,smax);
return 0;
}