Niuke 2021 summer training 4-j-average

Cattle guest 2021 Summer training 4-J-Average

Topic link

The question

Given n*m Matrix ,w[i][j]=a[i]+b[j], Find one not less than x * y The submatrix of , Its average value is the largest
n,m,ai,bi≤10⁵

Answer key

Suppose that the submatrix we require is
$$tot=\sum _{i=x1}^{x2}\sum _{j=y1}^{y2}(a_i+b_j)=(y2-y1+1)\ast \sum _{i=x1}^{x2}{a}_i+(x2-x1+1)\ast \sum _{j=y1}^{y2}{b}_j$$
that
$$ave=\frac{(y2-y1+1)\ast {\sum }_{i=x1}^{x2}{a}_i+(x2-x1+1)\ast {\sum }_{j=y1}^{y2}{b}_j}{(x2-x1+1)\ast (y2-y1+1)}=\frac{{\sum }_{i=x1}^{x2}{a}_i}{x2-x1+1}+\frac{{\sum }_{i=y1}^{y2}{b}_j}{y2-y1+1}$$
in other words , We just need to be right about a The array is continuous and its length is not less than x The maximum average of ,b Arrays are the same thing , Next, the key is how to find the maximum
Obviously, monotony can be considered . hypothesis q Medium is the average value of single subtraction , Traverse a i It can pop up q End less than with i Is the ending length is x Average value , To maintain monotony , Can prove that q The previous average plus the same value is still a single minus

DB Ave(int l,int r)
{
    
	return (sum[r]-sum[l-1])/(DB)(r-l+1);
}

for(int i=x;i<=n;i++)
{
    
	while(0<=t&&Ave(q[t],i)<Ave(i-x+1,i)) t--;
	q[++t]=i-x+1;
	ans1=max(ans1,Ave(q[0],i));
}

Code

#include<bits/stdc++.h>
#define LL long long
#define DB double
using namespace std;
const int N=1e5+9;
int n,m,x,y,t;
DB ans1,ans2;;
int q[N];
DB a[N],sum[N];
DB Ave(int l,int r)
{
    
	return (sum[r]-sum[l-1])/(DB)(r-l+1);
}
int main()
{
    
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++)
	{
    
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	t=-1;
	for(int i=x;i<=n;i++)
	{
    
		while(0<=t&&Ave(q[t],i)<Ave(i-x+1,i)) t--;
		q[++t]=i-x+1;
		ans1=max(ans1,Ave(q[0],i));
	}
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=m;i++)
	{
    
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	t=-1;
	memset(q,0,sizeof(q));
	for(int i=y;i<=m;i++)
	{
    
		while(0<=t&&Ave(q[t],i)<Ave(i-y+1,i)) t--;
		q[++t]=i-y+1;
		ans2=max(ans2,Ave(q[0],i));
	}
	printf("%.10lf",ans1+ans2);
	return 0;
}