离谱
查看原帖
离谱
1583598
Cristiano_Ronaldo_7楼主2024/12/20 20:02
#include <iostream>
#define int long long
using namespace std;
int n,m,a[5010][5010],id;
struct node{
	int ax1,ay1,ax2,ay2;
}e[25000010];
double ans,aans;
void dfs(int x1,int y1,int x2,int y2,double k){
	for(int i=1;i<=4;++i){
		if(i==1&&x1!=1){
			double tsum=0,tcnt=0,kp;
			for(int m=y1;m<=y2;++m){
				tsum+=a[x1-1][m];
				tcnt++;
			}
			kp=tsum/tcnt;
			if(kp>k){
				double tampans=(k*(x2-x1+1)*(y2-y1+1)*1.0+tsum)/((x2-x1+1)*(y2-y1+1)*1.0+tcnt);
				ans=max(ans,tampans);
				dfs(x1-1,y1,x2,y2,(k*(x2-x1+1)*(y2-y1+1)*1.0+tsum)/((x2-x1+1)*(y2-y1+1)*1.0+tcnt));
			}
		}
		if(i==2&&y1!=1){
			double tsum=0,tcnt=0,kp;
			for(int m=x1;m<=x2;++m){
				tsum+=a[m][y1-1];
				tcnt++;
			}
			kp=tsum/tcnt;
			if(kp>k){
				dfs(x1,y1-1,x2,y2,(k*(x2-x1+1)*(y2-y1+1)*1.0+tsum)/((x2-x1+1)*(y2-y1+1)*1.0+tcnt));
			}
		}
		if(i==3&&y2!=m){
			double tsum=0,tcnt=0,kp;
			for(int m=x1;m<=x2;++m){
				tsum+=a[m][y2+1];
				tcnt++;
			}
			kp=tsum/tcnt;
			if(kp>k){
				dfs(x1,y1-1,x2,y2,(k*(x2-x1+1)*(y2-y1+1)*1.0+tsum)/((x2-x1+1)*(y2-y1+1)*1.0+tcnt));
			}
		}
		if(i==4&&x2!=n){
			double tsum=0,tcnt=0,kp;
			for(int m=y1;m<=y2;++m){
				tsum+=a[x2+1][m];
				tcnt++;
			}
			kp=tsum/tcnt;
			if(kp>k){
				dfs(x1,y1-1,x2,y2,(k*(x2-x1+1)*(y2-y1+1)*1.0+tsum)/((x2-x1+1)*(y2-y1+1)*1.0+tcnt));
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n-1;++i){
		int ii=i+1;
		for(int j=1;j<=m-1;++j){
			int jj=j+1;
			double tampsum=0,tampcnt=0;
			for(int p=i;p<=ii;++p){
				for(int q=j;q<=jj;++q){
					tampcnt++;
					tampsum+=a[p][q];
				}
			}
			aans=max(aans,tampsum/tampcnt);
		}
	}
	for(int i=1;i<=n-1;++i){
		int ii=i+1;
		for(int j=1;j<=m-1;++j){
			int jj=j+1;
			double tampsum=0,tampcnt=0;
			for(int p=i;p<=ii;++p){
				for(int q=j;q<=jj;++q){
					tampcnt++;
					tampsum+=a[p][q];
				}
			}
			if(tampsum/tampcnt==aans){
				e[++id]=(node){i,ii,j,jj};
			}
		}
	}
	for(int i=1;i<=id;++i){
		dfs(e[i].ax1,e[i].ay1,e[i].ax2,e[i].ay2,aans);
	}
	cout<<ans;
	return 0;
}

这玩意放到a+b上能得20分

2024/12/20 20:02
加载中...