Cod sursa(job #48476)

Utilizator g3ppyStoian Vlad g3ppy Data 4 aprilie 2007 20:17:03
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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;

    }

sort (1,n);

ok=1;
i=1;
s=n;
smax=sum[n].x;

while (ok)
   {
   im=sum[i].j-sum[s].j;
   smin=sum[s].x-sum[i].x;
   if (im<0) im*=-1;
   if (smin>smax&&im+1>=k)
      {smax=smin;
       ok=0;
       }
   else if (im<k)
	 {
	 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;
}