QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #179443 | #7051. Largest Common Submatrix | linnins | WA | 1ms | 7864kb | C++20 | 2.0kb | 2023-09-14 21:24:46 | 2023-09-14 21:24:47 |
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);
}
printf(" ");
}
}
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7784kb
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: 7864kb
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: 1ms
memory: 7860kb
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 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 988124832 98812...
result:
wrong answer 1st numbers differ - expected: '80', found: '60'