QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1103#506798#7051. Largest Common SubmatrixwelikestudyingFluoresceSuccess!2024-11-01 23:20:292024-11-01 23:20:29

Details

Extra Test:

Wrong Answer
time: 1ms
memory: 7712kb

input:

2 2
1 2
3 4
1 4
2 3

output:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506798#7051. Largest Common SubmatrixFluoresceAC ✓110ms15740kbC++201.8kb2024-08-05 22:12:192024-11-04 16:53:49

answer

#include<bits/stdc++.h>
#include<unordered_map>
typedef long long ll;
typedef long double ld;
#define debug(a) cout<<a<<'\n'
#define Pll pair<ll,ll>
#define PII pair<int,int>
#define FI(i,b,e,s) for(int i=b;i<=e;i+=s)
#define FD(i,b,e,s) for(int i=b;i>=e;i-=s)
#define ft first
#define sd second
#define vec vector
using namespace std;
const int N = 1e3 + 10, M = 4e5, mod = 1e9 + 7;
const ll inf = 1e18;
const ld eps = 1e-8;
int mov[4][2] = { {0,1},{1,0},{-1,0},{0,-1} }, dx, dy;
ll n, m, k;
int a[N][N], rb[N*N];
int l[N], r[N], u[N][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	streambuf* cinbackup = cin.rdbuf(), * coubackup = cout.rdbuf();
	ifstream fin("in.txt");
	ofstream fout("out.txt");
	cin.rdbuf(fin.rdbuf());
	cout.rdbuf(fout.rdbuf());
#endif
	ll x, y, z, d;
	int _ = 1, __ = 1;
	//cin >> _;
	string s1, s;
	while (_--) {
		cin >> n >> m;
		int ans = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				cin >> a[i][j];
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				cin >> x;
				rb[x] = (i-1) * m + j;
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (rb[a[i][j]] - rb[a[i - 1][j]] == m)u[i][j] = u[i - 1][j] + 1;
				else u[i][j] = 1;
				l[j] = r[j] = j;
			}
			for (int j = 1; j <= m; ++j) {
				while (l[j] > 1 && u[i][j] <= u[i][l[j] - 1] && j - (l[j] - 1) == rb[a[i][j]] - rb[a[i][l[j] - 1]])l[j] = l[l[j] - 1];
			}
			for (int j = m; j >= 1; --j) {
				while (r[j] < m && u[i][j] <= u[i][r[j] + 1] && r[j]+1-j == rb[a[i][r[j] + 1]]-rb[a[i][j]])r[j] = r[r[j] + 1];
			}
			for (int j = 1; j <= m; ++j) {
				ans = max(ans, u[i][j] * (r[j] - l[j] + 1));
			}
		}
		cout << ans;
	}
	return 0;
}