POJ 2018 Best Cow Fences.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN=100000+10;

struct Point {
	int x, y;
	Point() {}
	Point(int x, int y):x(x), y(y){}
	bool operator / (Point oth) {
		return (LL)x*oth.y>=(LL)y*oth.x;
	}
	Point operator - (Point oth) {
		return Point(x-oth.x, y-oth.y);
	}
};

Point Q[MAXN];
int S[MAXN];
int N, F;

int main() {
	scanf("%d%d", &N, &F); S[0]=0;
	for (int i=1; i<=N; i++) {
		scanf("%d", &S[i]);
		S[i]=S[i]+S[i-1];
	}
	int head=0, tail=0; Q[0]=Point(0, 0);
	double ans=0;
	Point P;
	for (int i=F; i<=N; i++) {
		P=Point(i, S[i]);
		while (head<tail&&((Q[head+1]-Q[head])/(P-Q[head+1]))) head++;
		ans=max(ans, (double)(P.y-Q[head].y)/(P.x-Q[head].x));
		P=Point(i-F+1, S[i-F+1]);
		while (head<tail&&((P-Q[tail])/(Q[tail]-Q[tail-1]))) tail--;
		Q[++tail]=P;
	}
	int ret=1000*ans;
	printf("%d\n", ret);
	return 0;
}