zoj 3694 Arrangement

zoj 3694 Arrangement

#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>using namespace std;#define LL long longconst int maxn = 100005;const LL maxint = 1LL<<60;const double eps = 1e-5;int n,m,L,R;double a[maxn];double v[maxn];double dp[maxn][15];double sum[maxn];int q[maxn];int dblcmp(double a,double b){ if (fabs(a-b) < eps) return 0; return a < b ? -1 : 1;}double solve(double mid){ sum[0] = 0; for (int i=1;i<=n;i++) sum[i] = sum[i-1] + 1.0*a[i] - mid; for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) dp[i][j] = -maxint; for (int i=0;i<=n;i++) dp[i][0] = 0; for (int j=1;j<=m;j++) { int head = 0 , tail = 0; for (int i=j;i<=n;i++) { while (head < tail && i - q[head] > R) head++; int k = i - L; if (k >= 0) { while (head < tail && dblcmp(dp[q[tail-1]][j-1] - sum[q[tail-1]] , dp[k][j-1] - sum[k]) <= 0) tail--; q[tail++] = k; } dp[i][j] = dp[i-1][j]; if (head < tail) dp[i][j] = max(dp[i][j],dp[q[head]][j-1] + sum[i] - sum[q[head]]); } } return dp[n][m];}int main(){ while (scanf("%d%d%d%d",&n,&m,&L,&R)!=EOF) { double l = 1e30, r = -1e30; for (int i=1;i<=n;i++) { scanf("%lf",&a[i]); r = max(r,a[i]); l = min(l,a[i]); } bool flag = false; while (dblcmp(l,r) <= 0) { double mid = (l+r)/2.0; if (dblcmp(solve(mid),0) >= 0) { flag = true; l = mid + eps; } else r = mid - eps; } if (!flag) puts("-1"); else printf("%.2fn",floor(l*100)/100.0); } return 0;}