QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1103 | #506798 | #7051. Largest Common Submatrix | welikestudying | Fluoresce | Success! | 2024-11-01 23:20:29 | 2024-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'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#506798 | #7051. Largest Common Submatrix | Fluoresce | AC ✓ | 110ms | 15740kb | C++20 | 1.8kb | 2024-08-05 22:12:19 | 2024-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;
}