RT，此题 $O(n\times m \times \max(n,m))$ 过不了吗？

#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long
#define inf 998244353
#define lnf 0x3f3f3f3f3f3f3f3f

using namespace std;

const bool Debug = false;

//#define Debug true

namespace WTH {
	const int N = 1000 + 5;
	
	int n, m, c, f;
	char _Mp[N][N];
	int _Sm[N][N][2], _Ansc, _Ansf;
	
	void init () {
		memset (_Sm, 0, sizeof (_Sm));
		_Ansc = 0;
		_Ansf = 0;
	}
	
	void main () {
		cin >> n >> m >> c >> f;
		
//		if (Debug) {
//			cout << n << ' ' << m << ' ' << c << ' ' << f << endl;
//		}
//		
		for (register int i = 1; i <= n; ++ i) {
			for (register int j = 1; j <= m; ++ j) {
				cin >> _Mp[i][j];
			}
		}
		
		for (register int i = n; i; -- i) {
			for (register int j = m; j; -- j) {
				switch (_Mp[i][j]) {
					case '1' : {
						break ;
					}
					
					default : {
						_Sm[i][j][0] = _Sm[i + 1][j][0] + 1;
						_Sm[i][j][1] = _Sm[i][j + 1][1] + 1;
					}
				}
			}
		}
		
//		if (Debug) {
//			cout << "HHH" << endl;
//		}
//		
//		if (Debug) {
//			for (register int i = 1; i <= n; ++ i) {
//				for (register int j = 1; j <= m; ++ j) {
//					cout << i << ' ' << j << ' ' << _Sm[i][j][0] << ' ' << _Sm[i][j][1] << endl;
//				}
//			}
//		}
//		
		for (register int x = 1; x <= n; ++ x) {
			for (register int y = 1; y <= m; ++ y) {
				if (_Mp[x][y] ^ '0') {
					continue ;
				}
				
				for (register int l = 2; l < _Sm[x][y][0]; ++ l) {
					_Ansc += max (0ll, (_Sm[x][y][1] - 1) * (_Sm[x + l][y][1] - 1));
					_Ansc %= inf;
					_Ansf += max (0ll, (_Sm[x][y][1] - 1) * (_Sm[x + l][y][1] - 1) * (_Sm[x][y][0] - l - 1));
					_Ansf %= inf;
//					
//					if (Debug) {
//						cout << x << ' ' << y << ' ' << l << ' ' << _Sm[x][y][1] - 1 << ' ' << _Sm[x][y + l][1] - 1 << endl;
//						cout << _Sm[x][y][1] - 1 << ' ' << _Sm[x + l][y][1] - 1 << ' ' << _Sm[x][y][0] - l - 1 << endl;
//					}
				}
			}
		}
		
		cout << _Ansc * c << ' ' << _Ansf * f << endl;
	}
}

signed main () {
	ios :: sync_with_stdio (Debug);
	cin.tie (0);
	cout.tie (0);
	
	int T = 1, id;
	cin >> T >> id;
	
	while (T --) {
		WTH :: init ();
		WTH :: main ();
	}
	
	return 0;
}