QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #735480 | #7051. Largest Common Submatrix | gyydp123_LIM | WA | 0ms | 16176kb | C++20 | 1.6kb | 2024-11-11 20:17:08 | 2024-11-11 20:17:08 |
Judging History
answer
//Start: 2024-11-11 20:09:33
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1005;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int n,m,a[N][N],b[N][N];
pair<int,int>dl[N*N];
int l[N][N],r[N][N],u[N][N],d[N][N];
signed LJY(){
n=read();m=read();
For(i,1,n) For(j,1,m){
a[i][j]=read();
dl[a[i][j]].first+=i;
dl[a[i][j]].second+=j;
}For(i,1,n) For(j,1,m){
b[i][j]=read();
dl[b[i][j]].first-=i;
dl[b[i][j]].second-=j;
}
For(i,1,n){
l[i][1]=1;For(j,2,m) if(dl[a[i][j]]==dl[a[i][j-1]]) l[i][j]=l[i][j-1];else l[i][j]=j;
r[i][m]=m;ForDown(j,m-1,1) if(dl[a[i][j]]==dl[a[i][j+1]]) r[i][j]=r[i][j+1];else r[i][j]=j;
}For(i,1,m){
u[1][i]=1;For(j,2,n) if(dl[a[j][i]]==dl[a[j-1][i]]) u[j][i]=u[j-1][i];else u[j][i]=j;
d[n][i]=n;ForDown(j,n-1,1) if(dl[a[j][i]]==dl[a[j+1][i]]) d[j][i]=d[j+1][i];else d[j][i]=j;
}int ans=0;
For(i,1,n) For(j,1,m) if(l[i][j]==j)
For(x,j,r[i][j]){
int U=max(u[i][j],u[i][x]);
int D=min(d[i][j],d[i][x]);
ans=max(ans,(D-U+1)*(x-j+1));
}printf("%d",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14040kb
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:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 14116kb
input:
10 10 13 2 57 50 1 28 37 87 30 46 66 47 33 69 83 52 97 55 91 18 9 48 23 35 98 8 7 95 90 5 3 53 43 36 96 59 26 4 70 17 71 100 15 94 25 72 84 89 21 73 64 34 22 29 42 92 85 78 86 62 99 79 67 11 6 19 24 51 77 74 75 16 88 44 93 39 41 82 56 65 12 40 63 54 10 60 32 45 20 80 49 61 76 14 81 68 27 31 58 38 13...
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: 0
Accepted
time: 0ms
memory: 13952kb
input:
10 10 6 48 98 83 7 56 22 49 61 34 8 87 91 100 16 17 86 24 9 23 94 50 81 59 51 21 52 20 33 25 73 1 70 45 36 31 88 90 12 69 64 57 60 5 85 29 37 96 92 41 89 67 79 84 35 68 46 18 38 63 27 55 65 95 11 43 47 72 80 66 75 39 58 62 77 53 15 40 3 71 32 82 10 99 44 2 30 76 74 28 19 78 13 97 26 42 54 14 4 93 6 ...
output:
80
result:
ok 1 number(s): "80"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 16176kb
input:
10 10 37 16 29 24 14 20 41 63 4 15 71 99 17 26 33 47 83 55 89 52 32 22 95 44 81 93 78 31 42 12 94 70 25 46 18 97 57 62 68 67 21 69 54 27 13 96 64 48 59 28 11 49 9 73 100 90 85 36 2 58 74 53 98 34 7 5 3 91 23 76 77 86 84 92 50 51 45 61 30 66 35 1 10 79 39 6 80 82 43 88 75 60 38 87 40 8 19 56 72 65 37...
output:
100
result:
wrong answer 1st numbers differ - expected: '80', found: '100'