QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #1102 | #210631 | #7051. Largest Common Submatrix | welikestudying | yangqb | Failed. | 2024-11-01 23:19:30 | 2024-11-01 23:19:30 |
Details
Extra Test:
Accepted
time: 2ms
memory: 12120kb
input:
2 2 1 2 3 4 1 4 2 3
output:
2
result:
ok 1 number(s): "2"
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #210631 | #7051. Largest Common Submatrix | yangqb | WA | 162ms | 23836kb | C++20 | 952b | 2023-10-11 17:48:34 | 2024-11-04 16:53:19 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int lf[N][N];
int rg[N][N];
int up[N][N];
int a[N][N];
int b[N*N];
int main(){
int n,m;scanf("%d%d",&n,&m);
int x;
for(int i=1;i<=n*m;i++){
scanf("%d",&x);
b[x]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&x);
a[i][j]=b[x];
up[i][j]=1;
lf[i][j]=j;
rg[i][j]=j;
}
}
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
if(a[i][j]==a[i][j-1]+1){
lf[i][j]=lf[i][j-1];
}
}
}
for(int i=1;i<=n;i++){
for(int j=m-1;j>=1;j--){
if(a[i][j]==a[i][j+1]-1){
rg[i][j]=rg[i][j+1];
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>=2&&a[i][j]==a[i-1][j]+m){
up[i][j]=up[i-1][j]+1;
lf[i][j]=max(lf[i][j],lf[i-1][j]);
rg[i][j]=min(rg[i][j],rg[i-1][j]);
}
ans=max(ans,(rg[i][j]-lf[i][j]+1)*up[i][j]);
}
}
printf("%d\n",ans);
return 0;
}