Best Cow Fences POJ

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int sum[N],dp[N];
int q[N];
inline double calc(int j,int i) {
	return (double)(sum[i]-sum[j])/(i-j);
}
int main()
{
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		sum[0]=0;
		for(int i=1;i<=n;i++)
		{
			int val;
			scanf("%d", &val);
			sum[i]=sum[i-1]+val;
		}
		double ans=0;
		int l=1,r=0;
		q[1]=0;
		for(int i=k; i<=n; i++) {
			int j=i-k;
			while(l<r && calc(q[r], q[r-1] ) >=calc(i-k,q[r-1]))
				r--;
			q[++r]=j;
			while(l<r && calc(q[l+1],i)>=calc(q[l],i))
				l++;
			ans=max(ans,1.0*(sum[i]-sum[q[l]])/(i-q[l]) );
		}
		printf("%d
", (int)(ans*1000));
	}
 }