Cod sursa(job #48495)

Utilizator g3ppyStoian Vlad g3ppy Data 4 aprilie 2007 20:35:35
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#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;
}