QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242256 | #7051. Largest Common Submatrix | maghrabyJr_# | WA | 1ms | 3472kb | C++20 | 3.7kb | 2023-11-07 04:02:54 | 2023-11-07 04:02:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 10;
int ng[N], lg[N];
int32_t main() {
cin.tie(0);
cout.sync_with_stdio(0);
int n, m;
cin>>n>>m;
int a[n][m], mxUp[n][m], mxR[n][m], mxL[n][m];
pair<int,int> d[n][m];
map<int, pair<int,int>> mp;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int x; cin>>x;
mp[x]= {i, j};
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
assert(mp.find(a[i][j]) != mp.end());
auto [r, c] = mp[a[i][j]];
d[i][j]= {r - i, c - j};
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i && d[i][j] == d[i - 1][j]){
mxUp[i][j]= 1 + mxUp[i - 1][j];
}else{
mxUp[i][j]= 1;
}
if(j && d[i][j] == d[i][j - 1]){
mxL[i][j]= 1 + mxL[i][j - 1];
}else{
mxL[i][j]= 1;
}
}
for(int j = m - 1; j >= 0; j--){
if(j + 1 < m && d[i][j] == d[i][j + 1]){
mxR[i][j]= 1 + mxR[i][j + 1];
}else{
mxR[i][j]= 1;
}
}
}
int ans = 0;
for(int r = 0; r < n; r++)
{
for(int j = 0; j < m; j++){
ng[j] = m;
lg[j] = -1;
}
for(int j = 0; j < m; ){
vector<int> v;
int k = j;
while(d[r][k] == d[r][j]){
v.push_back(k);
++k;
}
stack<int> stk;
for(int u : v)
{
while(stk.size() && mxUp[r][stk.top()] <= mxUp[r][u]){
ng[stk.top()]= u;
stk.pop();
}
stk.push(u);
}
while(stk.size()) stk.pop();
reverse(v.begin(), v.end());
for(int u : v)
{
while(stk.size() && mxUp[r][stk.top()] <= mxUp[r][u]){
lg[stk.top()]= u;
stk.pop();
}
stk.push(u);
}
j = k;
}
for(int j = 0; j < m; j++)
{
int LC = max(lg[j] + 1, j - mxL[r][j] + 1), RC = min(ng[j] - 1, j + mxR[r][j] - 1);
ans= max(ans, (RC - LC + 1) * mxUp[r][j]);
}
}
cout<<ans<<"\n";
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3472kb
input:
3 4 5 6 7 8 1 2 3 4 9 10 11 12 5 6 8 7 1 2 4 3 12 11 10 9
output:
2
result:
wrong answer 1st numbers differ - expected: '4', found: '2'