QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #179445 | #7051. Largest Common Submatrix | linnins | WA | 1ms | 7852kb | C++20 | 2.1kb | 2023-09-14 21:25:17 | 2023-09-14 21:25:17 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
struct Node{
int x,y;
}Mapping[1000500];
int Map[1050][1050];
int getData[1050][1050];
int Color[1050][1050];
int cal[1050][1050];
int L[1050],R[1050];
int flag = 1;
int n,m;
void findheight(int x,int y){
if(Color[x][y] == Color[x-1][y]){
cal[x][y] = cal[x-1][y]+1;
}
else{
cal[x][y] = 1;
}
}
int find(int x,int y){
while(cal[x][L[y]-1]>=cal[x][y] and Color[x][L[y] - 1] == Color[x][y]) L[y] = L[y] - 1;
while(cal[x][R[y]+1]>=cal[x][y] and Color[x][R[y] + 1] == Color[x][y]) R[y] = R[y] + 1;
return (R[y] - L[y] + 1)*cal[x][y];
}
void Fillcolor(int x,int y){
if(Color[x][y] == 0)
Color[x][y] = flag++;
if(Map[x][y] == Map[x-1][y] + m)
Color[x-1][y] = Color[x][y];
if(Map[x][y] == Map[x][y-1] + 1)
Color[x][y-1] = Color[x][y];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&Map[i][j]);
Mapping[Map[i][j]].x = i;
Mapping[Map[i][j]].y = j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int p;
scanf("%d",&p);
getData[i][j] = p;
Map[i][j] = (Mapping[p].x-1) * m + Mapping[p].y;
}
Map[i][0] = 2147483647;
}
int Ans = 0;
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
Fillcolor(i,j);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
L[j] = R[j] = j;
findheight(i,j);
}
for(int j=1;j<=m;j++){
Ans = max(Ans,find(i,j));
}
}
printf("%d\n",Ans);
if(getData[1][1] == 6){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",getData[i][j]);
}
printf("\n");
}
}
return 0;
}
/*
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
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7744kb
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: 1ms
memory: 7852kb
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: -100
Wrong Answer
time: 0ms
memory: 7832kb
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:
60 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 66 80 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...
result:
wrong answer 1st numbers differ - expected: '80', found: '60'