기울기 dp

사고방식: 직접 사율 최적화를 통해 해답을 구한다.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#define Maxn 1000010

using namespace std;

__int64 sum[Maxn];

__int64 num[Maxn];

int que[Maxn*4];

int main()

{

    int n,k,head,rear,x;

    int i,j;

    double ans;

    while(scanf("%d%d",&n,&k)!=EOF){

        ans=0;

        for(i=1;i<=n;i++){

            scanf("%I64d",&num[i]);

            sum[i]=sum[i-1]+num[i];

        }

        head=1,rear=0;

        que[++rear]=0;

        for(i=k;i<=n;i++){

            j=i-k+1;

            while(head<rear&&(sum[i]-sum[que[head+1]])*(i-que[head])>=(sum[i]-sum[que[head]])*(i-que[head+1]))

                head++;

            ans=max(ans,(double)((double)sum[i]-(double)sum[que[head]])/(double)((double)i-(double)que[head]));

            while(head<rear&&(sum[j]-sum[que[rear]])*(que[rear]-que[rear-1])<=(sum[que[rear]]-sum[que[rear-1]])*(j-que[rear]))

                rear--;

            que[++rear]=j;

        }

        printf("%.2lf
",ans);

    }

    return 0;

}