QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #522072 | #7051. Largest Common Submatrix | LuCiiiD | TL | 2ms | 12124kb | C++23 | 1.9kb | 2024-08-16 18:09:03 | 2024-08-16 18:09:03 |
Judging History
answer
#include <bits/stdc++.h>
#define MAX 1500005
using namespace std;
int N, M, ans, L[MAX], R[MAX], H[MAX], a[1005][1005], b[1005][1005];
pair<int,int>dis[MAX];
inline void read(int &a);
signed main()
{
read(N), read(M);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
read(a[i][j]), dis[a[i][j]] = {i, j};
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
read(b[i][j]);
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
int a_broad, b_broad, idx = i + j * 1005;
pair<int, int> a_dis = dis[b[i][j]];
a_broad = a_dis.second, b_broad = j;
while (a_broad - 1 >= 1 && b_broad - 1 >= 1 && a[a_dis.first][a_broad - 1] == b[i][b_broad - 1])
L[idx]++, a_broad--, b_broad--;
a_broad = a_dis.second, b_broad = j;
while (a_broad + 1 <= M && b_broad + 1 <= M && a[a_dis.first][a_broad + 1] == b[i][b_broad + 1])
R[idx]++, a_broad++, b_broad++;
}
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
pair<int, int> a_dis = dis[b[i][j]];
int idx = i + j * 1005, idx_pre_b = i - 1 + j * 1005;
if (i - 1 >= 1 && a_dis.first - 1 >= 1 && a[a_dis.first - 1][a_dis.second] == b[i - 1][j])
L[idx] = min(L[idx_pre_b], L[idx]), R[idx] = min(R[idx_pre_b], R[idx]), H[idx] = H[idx_pre_b] + 1;
ans = max(ans, (L[idx] + R[idx] + 1) * (H[idx] + 1));
}
}
printf("%d\n", ans);
}
void read(int &a)
{
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
a = s * w;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12052kb
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: 2ms
memory: 11980kb
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: 12028kb
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: 0
Accepted
time: 0ms
memory: 12084kb
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:
80
result:
ok 1 number(s): "80"
Test #5:
score: 0
Accepted
time: 1ms
memory: 12104kb
input:
10 10 22 71 28 19 15 47 31 88 95 85 56 79 87 43 96 39 45 97 83 36 6 21 98 34 65 91 58 62 41 42 26 37 74 8 27 55 84 75 20 35 49 24 51 32 50 68 52 5 10 11 25 73 38 92 63 67 64 13 46 78 57 53 23 54 16 99 17 40 82 30 61 81 48 7 86 4 3 60 93 76 90 18 29 44 1 100 2 69 9 12 80 70 33 94 66 72 77 14 59 89 22...
output:
24
result:
ok 1 number(s): "24"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11960kb
input:
10 10 35 58 83 13 75 51 32 97 76 6 63 96 52 77 65 59 90 86 68 9 22 16 56 74 100 91 44 66 8 79 28 21 17 94 31 60 25 24 64 14 55 71 81 67 53 7 95 41 30 40 78 54 48 10 34 47 3 70 98 38 61 89 42 49 50 20 45 18 62 27 73 15 37 84 57 33 88 2 82 72 85 29 80 26 43 39 92 1 93 19 99 11 5 69 87 12 46 4 23 36 97...
output:
24
result:
ok 1 number(s): "24"
Test #7:
score: 0
Accepted
time: 2ms
memory: 12104kb
input:
10 10 15 53 47 95 2 80 94 98 17 99 34 37 89 59 49 41 25 29 79 84 45 42 19 20 70 40 4 73 58 76 51 81 87 65 3 10 1 93 27 38 39 96 13 63 8 30 35 68 52 5 75 83 18 88 9 100 92 14 22 46 32 72 69 6 11 12 90 86 62 48 82 61 60 74 71 44 43 16 23 57 26 21 91 64 77 33 55 24 54 78 28 7 36 85 50 31 56 67 97 66 45...
output:
60
result:
ok 1 number(s): "60"
Test #8:
score: 0
Accepted
time: 1ms
memory: 12012kb
input:
10 10 11 17 94 61 73 42 79 40 2 7 35 96 24 100 85 46 22 9 98 97 51 44 27 14 48 21 33 36 45 34 56 4 39 6 63 75 74 54 57 66 59 37 10 93 58 78 89 72 55 30 64 32 68 83 38 90 99 67 69 95 49 41 91 71 5 19 26 47 80 52 84 70 13 20 77 12 8 86 88 82 16 43 50 25 53 1 29 81 76 92 28 18 31 87 3 15 65 60 62 23 11...
output:
4
result:
ok 1 number(s): "4"
Test #9:
score: 0
Accepted
time: 1ms
memory: 12124kb
input:
12 12 19 131 48 26 21 108 103 84 110 144 49 24 22 35 8 47 34 138 7 142 100 13 79 126 82 31 94 58 74 61 56 99 101 96 67 109 81 5 43 38 54 10 83 107 16 50 133 97 59 68 72 117 113 14 116 6 4 44 111 91 28 69 136 135 71 30 129 52 139 25 125 9 88 40 1 51 86 66 62 76 105 78 102 70 87 137 64 93 41 118 124 3...
output:
4
result:
ok 1 number(s): "4"
Test #10:
score: 0
Accepted
time: 1ms
memory: 12072kb
input:
12 12 144 73 133 126 22 86 83 13 120 62 101 39 26 7 141 125 3 40 99 140 114 28 68 27 42 17 85 35 71 50 46 45 5 14 47 2 49 9 88 32 18 97 29 95 8 109 1 76 111 48 60 132 20 115 138 43 135 112 4 92 55 143 127 52 117 36 84 107 110 15 105 104 74 37 102 129 108 23 98 38 19 122 6 59 33 90 118 89 116 11 56 1...
output:
16
result:
ok 1 number(s): "16"
Test #11:
score: 0
Accepted
time: 1ms
memory: 11980kb
input:
10 10 89 28 86 9 59 70 49 5 8 47 65 84 42 99 27 44 90 62 24 25 12 95 81 21 58 66 37 76 20 68 34 87 77 18 26 11 61 45 96 51 60 80 64 32 53 19 78 38 30 3 13 63 79 48 46 82 55 93 15 40 100 41 71 36 16 83 14 52 98 10 73 17 91 50 7 67 6 75 74 1 22 43 33 54 31 72 85 88 39 23 4 92 2 35 69 57 94 56 29 97 72...
output:
2
result:
ok 1 number(s): "2"
Test #12:
score: -100
Time Limit Exceeded
input:
1000 1000 145656 791628 740559 132604 88206 427138 947611 103465 802534 882213 161554 408446 198824 194485 228763 373358 414907 364727 747248 222571 971478 217962 525156 244261 193496 681387 978458 994637 413901 206046 663949 547415 151899 508035 778005 977645 576922 604407 537722 999374 62502 54059...