QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #268247 | #7051. Largest Common Submatrix | 8BQube# | WA | 1ms | 11596kb | C++20 | 1.7kb | 2023-11-28 14:17:50 | 2023-11-28 14:17:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())
int arr[1005][1005], brr[1005][1005];
int up[1005][1005], lft[1005];
pii pos[1000005];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> arr[i][j];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
cin >> brr[i][j];
pos[brr[i][j]] = pii(i, j);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
up[i][j] = 1;
auto [x, y] = pos[arr[i][j]];
if (i > 1 && brr[x - 1][y] == arr[i - 1][j])
up[i][j] += up[i - 1][j];
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
vector<int> stk;
for (int j = 1; j <= m; ++j) {
auto [x, y] = pos[arr[i][j]];
if (j == 1 || brr[x][y - 1] != arr[i][j - 1])
vector<int>(1, j - 1).swap(stk);
while (SZ(stk) > 1 && up[i][j] <= up[i][stk.back()])
stk.pop_back();
lft[j] = j - stk.back();
}
for (int j = m; j >= 1; --j) {
auto [x, y] = pos[arr[i][j]];
if (j == m || brr[x][y + 1] != arr[i][j + 1])
vector<int>(1, j + 1).swap(stk);
while (SZ(stk) > 1 && up[i][j] <= up[i][stk.back()])
stk.pop_back();
ans = max(ans, (lft[j] + stk.back() - j - 1) * up[i][j]);
}
}
cout << ans << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9560kb
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: 11596kb
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: 9508kb
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:
100
result:
wrong answer 1st numbers differ - expected: '80', found: '100'