QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #523500 | #7051. Largest Common Submatrix | CharwingHawk | WA | 2ms | 16216kb | C++17 | 2.5kb | 2024-08-18 12:31:36 | 2024-08-18 12:31:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fuck cout<<"fuck "
#define _ <<' '<<
#define __ <<' '
#define __l <<'\n'
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define Mod(x) ((x) %MOD +MOD) %MOD
#define int long long
#define append push_back
const int INF = 6452864528;
const int N = 1e3 + 10;
const int MatN = 3;
const int MOD = 998244353;
int tin,tinn,tinnn,tmp;string stin,stinn,stinnn;int itr;
// ---
int a[N][N],b[N][N];
int h[N][N],l[N][N],r[N][N];
int color[N][N],colors = 0;
// ---
void solve(){
int n,m; cin>>n>>m;
unordered_map <int, int> cast;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
cast[a[i][j]] = (i-1)*m+j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>b[i][j];
if (j>1 && cast[b[i][j]]-cast[b[i][j-1]] == 1){
color[i][j] = color[i][j-1];
}
else if (i>1 && cast[b[i][j]]-cast[b[i-1][j]] == m){
color[i][j] = color[i-1][j];
}
else{
color[i][j] = ++colors;
}
}
}
int res = 0;
for (int tgt=1;tgt<=colors;tgt++){
int ans = 0;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
h[i][j] = 1;
r[i][j] = l[i][j] = j;
}
for(int j=1+1;j<=m;j++)
if (color[i][j] == tgt && color[i][j-1] == tgt)
l[i][j] = l[i][j-1];
for(int j=m-1;j>=1;j--)
if (color[i][j] == tgt && color[i][j+1] == tgt)
r[i][j] = r[i][j+1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if (i>1 && color[i][j] == tgt){
if (color[i-1][j] == tgt){
h[i][j] = h[i-1][j] + 1;
l[i][j] = max(l[i][j], l[i-1][j]);
r[i][j] = min(r[i][j], r[i-1][j]);
}
ans = max(ans, (r[i][j] - l[i][j] + 1) * h[i][j]);
}
}
}
res = max(res,ans);
}
cout<<res;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<color[i][j] __;
// }
// cout __l;
// }
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//cout<<fixed<<setprecision(3);
signed o_O = 1;
// cin>>o_O;
while (o_O--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 15868kb
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: 16008kb
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: 2ms
memory: 14088kb
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: 13860kb
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: 2ms
memory: 15944kb
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: 14088kb
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: 14088kb
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: 0ms
memory: 14160kb
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: 2ms
memory: 16216kb
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: -100
Wrong Answer
time: 1ms
memory: 13872kb
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:
10
result:
wrong answer 1st numbers differ - expected: '16', found: '10'