记录编号	377749	评测结果	AAAAAAAAAA
题目名称	[USACO Mar03]最大平均值	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2017-03-02 01:51:37	内存使用	1.30 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <cctype>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;}
  inline int readint(){
    char c; int r; bool s = false;
    while(c = readc()){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
  }
}; using IO::readint;
#define MAXN 100002
int sum[MAXN];
int q[MAXN];
double getk(int l, int r){
  return (sum[r]-sum[l-1])*1.0/(r-l+1);
}                                                                              
int main(){
  freopen("avanum.in", "r", stdin);
  freopen("avanum.out", "w", stdout);
  int n = readint(); int k = readint();
  sum[0] = 0;
  for(int i = 1; i <= n; i++)
    sum[i] = sum[i-1]+readint();
  double res = -1e15;
  int h = 0, t = -1;
  for(int i = k; i <= n; i++){
    while(h <= t && q[h] > i-k)h++;
    while(h <= t && getk(q[t], i) < getk(i-k+1, i))t--;
    q[++t] = i-k+1;
    res = max(res, getk(q[h], i));
  }
  printf("%d\n", int(res*1000));
  return 0;
}