Cod sursa(job #48530)

Utilizator g3ppyStoian Vlad g3ppy Data 4 aprilie 2007 21:19:50
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 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,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;
}