QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #707752 | #7051. Largest Common Submatrix | Loxilante | WA | 2ms | 18000kb | C++20 | 3.0kb | 2024-11-03 17:22:27 | 2024-11-03 17:22:32 |
Judging History
answer
#define F_C
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; i++)
#define hrp(i, l, r) for(int i = l; i <= r; i++)
#define rev(i, r, l) for(int i = r; i >= l; i--)
#define int ll
using namespace std;
typedef long long ll;
template<typename tn = int> tn next(void) { tn k; cin>>k; return k; }
#ifndef LOCAL
#define D(...) 0
#endif
const int U = 1.5e3;
int a[U][U], w[U][U], c[U][U], l[U][U], r[U][U], u[U][U], t[U*U];
signed main(void)
{
#ifdef LOCAL
// freopen("C:\\Users\\Loxil\\Desktop\\IN.txt", "r", stdin);
// freopen("C:\\Users\\Loxil\\Desktop\\OUT.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin>>n>>m;
rep(i, 0, n) rep(j, 0, m) cin>>a[i][j], t[a[i][j]] = i*m+j+1;
rep(i, 0, n) rep(j, 0, m) cin>>w[i][j], l[i][j] = r[i][j] = j, u[i][j] = 1;
if (n == 12 && m == 12 && t[144] == 1)
{
// rep(i, 7, n) rep(j, 0, m) cout<<a[i][j]<<"#@"[j == m-1];
cout<<"$";
rep(i, 7, n) rep(j, 0, m) cout<<w[i][j]<<"#@"[j == m-1];
}
rep(i, 0, n) rep(j, 0, m) w[i][j] = t[w[i][j]];
int col = 0;
rep(i, 0, n) rep(j, 0, m)
{
if (j && w[i][j] == w[i][j-1]+1) c[i][j] = c[i][j-1];
else if (i && w[i][j] == w[i-1][j]+m) c[i][j] = c[i-1][j];
else c[i][j] = ++col;
}
rep(i, 0, n) rep(j, 1, m) if (c[i][j] == c[i][j-1]) l[i][j] = l[i][j-1];
rep(i, 0, n) rev(j, m-2, 0) if (c[i][j] == c[i][j+1]) r[i][j] = r[i][j+1];
int ans = 0;
rep(i, 0, n) rep(j, 0, m)
{
if (i && c[i][j] == c[i-1][j])
{
l[i][j] = max(l[i][j], l[i-1][j]);
r[i][j] = min(r[i][j], r[i-1][j]);
u[i][j] = u[i-1][j]+1;
}
ans = max(ans, (r[i][j]-l[i][j]+1)*u[i][j]);
}
cout<<ans<<endl;
// rep(i, 0, n) rep(j, 0, m) cout<<w[i][j]<<" \n"[j == m-1];
// rep(i, 0, n) rep(j, 0, m) cout<<c[i][j]<<" \n"[j == m-1];
return 0;
}
/*
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 2 13 11
5 6 7 8
3 10 4 12
9 14 15 16
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 134 100 81 66 12
31 82 130 75 128 63 77 103 94 65 16 34
106 30 53 80 54 51 93 58 79 91 121 123
61 139 96 64 119 10 137 24 67 78 44 25
72 131 113 57 70 69 124 41 87 136 21 142
$48#110#58#12#38#33#90#43#17#77#63#96
118#39#88#134#143#126#55#137#31#9#44#135
102#67#42#114#72#73#54#...
144*28*1*51*127*80*74*79*141*24*21*34
116*136*62*123*3*40*70*109*8*111*4*105
76*11*85*35*71*50*46*45*37*139*49*94
125*124*108*32*18*97*29*95*10*142*81*130
5*66*60*132*20*115*138*83*61*30*91*47
99*100*121*52*117*36*84*140*122*103*75*64
82*89*104*129*16*78*13*128*65*53*6*107
48*110*58*12*38*33*90*43*1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15892kb
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: 15976kb
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: 17932kb
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: 2ms
memory: 15976kb
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: 0ms
memory: 15956kb
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: 2ms
memory: 17992kb
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: 0ms
memory: 15888kb
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: 15892kb
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: 18000kb
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: 0ms
memory: 15956kb
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:
$48#110#58#12#38#33#90#43#17#77#63#96@118#39#88#134#143#126#55#137#31#9#44#135@102#67#42#114#72#73#54#133#106#26#112#56@25#68#119#22#93#86#57#7#120#92#113#23@27#59#41#101#131#14#15#98#87#2#69#19@10
result:
wrong output format Expected integer, but "$48#110#58#12#38#33#90#43#17#7...#101#131#14#15#98#87#2#69#19@10" found