Combination of Physics and Maths

サブマトリクスのすべての数の和をサブマトリクスの最後の行の和で除算して最大にし、この比を出力するように、サブマトリクスを求めます.
各列について、最初の行から終了行(任意の行)までの数の和を終了行の数で割った場合、各列の一部の行を行列の最大値とし、複数の列を行列とした場合、マージ後の値は必ずマージ前の値より大きくないため、計算を行います.

	     a/b,    c/d;
	    (a+c)/(b+d);
	a/b=(a*b+a*d)/(b*b+b*d);
	(a+c)/(b+d)=(a*b+c*b)/(b*b+b*d);
	a/b-(a+c)/(b+d)=(a*d-c*b)/(b*b+b*d);
	a/b>c/d=>a/b-c/d=(a*d-b*c)/b*d>0=>a*d>b*c;
	  a/b-(a+c)/(b+d)=(a*d-c*b)/(b*b+b*d)>0;
	 a/b>(a+c)/(b+d)
	  a/b=c/d,    =

従って,単一列の最大値を探すだけで,総使用時間はO(Tnm)である.

#include
#include
#include

using namespace std;

const int N = 440;

int date[N];


int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		memset(date, 0, sizeof(date));
		int n,m;
		scanf("%d %d", &n,&m);
		double ans;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				int temp;
				scanf("%d", &temp);
				date[j] += temp;
				ans = max(ans, 1.0*date[j] / temp);
			}
		}
		printf("%.8lf
", ans);
	}
}