QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #522066 | #7051. Largest Common Submatrix | LuCiiiD | WA | 2ms | 14156kb | C++23 | 1.9kb | 2024-08-16 18:04:21 | 2024-08-16 18:04:22 |
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> ID[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]), ID[i + j * 1005].first = i, ID[i + j * 1005].second = 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 = ID[idx];
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++)
{
int idx = i + j * 1005, idx_pre_b = (i - 1) + j * 1005;
pair<int, int> a_dis = ID[i + 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: 2ms
memory: 12088kb
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: 12128kb
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: 12140kb
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: 1ms
memory: 12068kb
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: -100
Wrong Answer
time: 1ms
memory: 14156kb
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:
10
result:
wrong answer 1st numbers differ - expected: '24', found: '10'