QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #242269 | #7051. Largest Common Submatrix | maghrabyJr_ | TL | 0ms | 3824kb | C++20 | 3.4kb | 2023-11-07 04:46:46 | 2023-11-07 04:46:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 10;
int nxt[N], lst[N];
int32_t main() {
cin.tie(0);
cout.sync_with_stdio(0);
int n, m;
cin>>n>>m;
int a[n][m], mxUp[n][m], mxR[n][m], mxL[n][m];
pair<int,int> d[n][m];
map<int, pair<int,int>> mp;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int x; cin>>x;
mp[x]= {i, j};
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
assert(mp.find(a[i][j]) != mp.end());
auto [r, c] = mp[a[i][j]];
d[i][j]= {r - i, c - j};
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i && d[i][j] == d[i - 1][j]){
mxUp[i][j]= 1 + mxUp[i - 1][j];
}else{
mxUp[i][j]= 1;
}
if(j && d[i][j] == d[i][j - 1]){
mxL[i][j]= 1 + mxL[i][j - 1];
}else{
mxL[i][j]= 1;
}
}
for(int j = m - 1; j >= 0; j--){
if(j + 1 < m && d[i][j] == d[i][j + 1]){
mxR[i][j]= 1 + mxR[i][j + 1];
}else{
mxR[i][j]= 1;
}
}
}
int ans = 0;
for(int r = 0; r < n; r++)
{
for(int j = 0; j < m; j++){
nxt[j] = m;
lst[j] = -1;
}
{
stack<int> stk;
for(int u = 0; u < m; u++){
while(stk.size() && mxUp[r][stk.top()] > mxUp[r][u]){
nxt[stk.top()]= u;
stk.pop();
}
stk.push(u);
}
}
{
stack<int> stk;
for(int u = m - 1; u >= 0; u--){
while(stk.size() && mxUp[r][stk.top()] > mxUp[r][u]){
lst[stk.top()]= u;
}
stk.push(u);
}
}
for(int j = 0; j < m; j++)
{
int LC = max(lst[j] + 1, j - mxL[r][j] + 1);
int RC = min(nxt[j] - 1, j + mxR[r][j] - 1);
ans= max(ans, (RC - LC + 1) * mxUp[r][j]);
}
}
cout<<ans<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
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: 3632kb
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: 3824kb
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: -100
Time Limit Exceeded
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...