QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #521979 | #7051. Largest Common Submatrix | QFshengxiu# | TL | 983ms | 82180kb | C++20 | 3.5kb | 2024-08-16 17:03:30 | 2024-08-16 17:03:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define pb push_back
#define fi first
#define se second
#define sz(x) x.size()
#define lowbit(x) (x & (-x))
#define all(x) x.begin(), x.end()
#define inf 0x3f3f3f3f3f3f3f3f
// #define int long long
#define pai 3.14
#define QF ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define c1 cout << 1
#define c2 cout << 2
// #define width cout << ""
using ll = long long;
using PII = pair<int, int>;
using LD = long double;
mt19937_64 rnd(chrono::duration_cast<chrono::nanoseconds>(chrono::system_clock::now().time_since_epoch()).count());
constexpr int N = 1e3 + 10;
int n, m;
int a[N][N], b[N][N], row[N][N], col[N][N], h[N], width[N];
int stk[N], kuan[N];
map<int, PII> mp;
void solve()
{
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];
mp[b[i][j]] = {i, j};
}
}
for (int i = 1; i <= m; i++)
{
int pos = 1;
while (pos <= n)
{
int j = pos + 1;
int deta = 1;
auto [x, y] = mp[a[pos][i]];
while (j <= n && x + deta <= n)
{
deta = j - pos;
if (a[j][i] == b[x + deta][y])
{
j++;
}
else
break;
}
for (int w = pos; w < j; w++)
{
col[w][i] = j - w;
}
pos = j;
}
}
int id;
int ans = -1;
for (int _ = 1; _ <= n; _++)
{
for (int j = 1; j <= m; j++)
{
h[j] = col[_][j];
// cout << h[j] << " ";
}
// cout << endl;
stk[0] = h[m + 1] = id = 0;
for (int i = 1; i <= m + 1; i++)
{
if (id)
{
auto [x, y] = mp[a[_][i]];
if (a[_][i - 1] != b[x][y - 1])
{
int w = 0;
for (int i = 1; i <= id; i++)
{
w += width[i];
}
ans = max(ans, stk[1] * w);
id = 0;
stk[++id] = h[i];
width[id] = 1;
ans = max(ans, h[i]);
continue;
}
}
if (h[i] > stk[id])
{
stk[++id] = h[i];
width[id] = 1;
}
else
{
int w = 0;
while (stk[id] > h[i])
{
w += width[id];
ans = max(ans, w * stk[id]);
id--;
}
stk[++id] = h[i];
width[id] = w + 1;
}
// cout << ans << endl;
}
}
cout << ans;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= m; j++)
// {
// cout << col[i][j] << " ";
// }
// cout << endl;
// }
}
signed main()
{
QF;
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
// cout << endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7852kb
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: 7908kb
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: 1ms
memory: 7768kb
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: 7776kb
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: 7832kb
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: 1ms
memory: 7768kb
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: 1ms
memory: 7776kb
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: 7776kb
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: 0ms
memory: 7756kb
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: 0ms
memory: 7832kb
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: 0ms
memory: 7772kb
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: 0
Accepted
time: 983ms
memory: 82180kb
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...
output:
1000000
result:
ok 1 number(s): "1000000"
Test #13:
score: 0
Accepted
time: 982ms
memory: 79980kb
input:
1000 1000 834264 617630 804453 55758 887929 710187 983995 537648 412974 189468 702697 792339 791361 697740 501608 611911 695540 929085 106655 515172 67349 499726 855097 527613 193542 954358 868521 103306 178517 645631 689409 588682 426918 965958 347115 180933 933208 129629 471469 236249 560194 86873...
output:
888000
result:
ok 1 number(s): "888000"
Test #14:
score: -100
Time Limit Exceeded
input:
1000 1000 894204 922634 641738 426212 799590 748573 191782 123346 800500 11798 525443 111932 224897 541191 482575 709497 534061 940819 479215 375276 799859 936003 825761 629886 13572 192641 615652 931690 906911 937429 279445 395821 896441 78960 492938 865513 234692 905707 416821 535693 639924 841267...
output:
888000