QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #525440 | #7051. Largest Common Submatrix | Terryjoy | WA | 2ms | 11848kb | C++14 | 1.8kb | 2024-08-20 16:38:22 | 2024-08-20 16:38:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int n, m, f[maxn][maxn], a[maxn][maxn], b[maxn][maxn], L[maxn][maxn], R[maxn][maxn];
pair<int, int> pw[maxn * maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
cin >> b[i][j], pw[b[i][j]] = {i, j};
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int val = a[i][j];
f[i][j] = (b[pw[val].first - 1][pw[val].second] == a[i - 1][j] ? f[i - 1][j] : 0) + 1;
R[i][j] = L[i][j] = j;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = m - 1; j; --j) {
int val = a[i][j];
R[i][j] = b[pw[val].first][pw[val].second + 1] == a[i][j + 1] ? R[i][j + 1] : j;
}
for (int j = 2; j <= m; ++j) {
int val = a[i][j];
L[i][j] = b[pw[val].first][pw[val].second - 1] == a[i][j - 1] ? L[i][j - 1] : j;
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j) {
// cout << i << " " << j << " " << L[i][j] << " " << R[i][j] << " >>\n";
// }
// }
int ans = 0;
for (int i = 1; i <= n; ++i) {
vector<int> q;
for (int j = 1; j <= m; ++j) {
while (q.size() && a[i][q.back()] > a[i][j]) {
R[i][q.back()] = min(R[i][q.back()], j - 1);
q.pop_back();
}
q.push_back(j);
}
for (int j = m; j; --j) {
while (q.size() && a[i][q.back()] > a[i][j]) {
L[i][q.back()] = max(L[i][q.back()], j + 1);
q.pop_back();
}
}
for (int j = 1; j <= m; ++j) {
ans = max(ans, f[i][j] * (R[i][j] - L[i][j] + 1));
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j) {
// cout << i << " " << j << " " << L[i][j] << " " << R[i][j] << " <<\n";
// }
// }
cout << ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11800kb
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: 11848kb
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: 11848kb
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:
90
result:
wrong answer 1st numbers differ - expected: '80', found: '90'