QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#523835 | #7051. Largest Common Submatrix | Tahmid76 | WA | 2ms | 13872kb | C++14 | 3.0kb | 2024-08-18 19:27:40 | 2024-08-18 19:27:40 |
Judging History
answer
//And He found you lost and guided [you] [93:07]
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef map<int,int> mpi;
typedef map<ll,ll> mpl;
typedef unordered_map<int,int> umpi;
typedef unordered_map<ll,ll> umpl;
#define modu 998244353
#define mod 1000000007
#define eps 1e-7
#define inf 1000000000000000006
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
// #define pi acos(-1.0)
#define dec(n) fixed << setprecision(n)
#define N 500005
#define int long long
int n,m,a[1005][1005],b[1005][1005];
pair<int,int> c[1005][1005];
pair<int,int> mp[1000005];
pair<int,int> ans[1005][1005];
int val[1005][1005];
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<=n;i++){
for(int j=1;j<=m;j++){
c[i][j]={mp[a[i][j]].ff-i,mp[a[i][j]].ss-j};
if(i==1) val[i][j]=1;
else{
if(c[i-1][j]==c[i][j]) val[i][j]=val[i-1][j]+1;
else val[i][j]=1;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
int lst[1005],dst[1005];
stack<pair<int,int>> st;
for(int j=1;j<=m;j++){
if(c[i][j-1]!=c[i][j]){
while(!st.empty()) st.pop();
st.push({0,j-1});
}
while(!st.empty() && st.top().ff>=val[i][j]) st.pop();
if(!st.empty()) lst[j]=st.top().ss;
else lst[j]=j-1;
st.push({val[i][j],j});
}
while(!st.empty()) st.pop();
for(int j=m;j>0;j--){
if(c[i][j+1]!=c[i][j]){
while(!st.empty()) st.pop();
st.push({0,j+1});
}
while(!st.empty() && st.top().ff>=val[i][j]) st.pop();
if(!st.empty()) dst[j]=st.top().ss;
else dst[j]=j+1;
st.push({val[i][j],j});
}
for(int j=1;j<=m;j++){
// cout << val[i][j] << " " << dst[j] << " " << lst[j] << " - ";
ans=max(ans,(dst[j]-lst[j]-1)*val[i][j]);
}
// cout << endl;
}
cout << ans << endl;
}
signed main(){
fastio;
//srand(chrono::steady_clqk::now().time_since_epqh().count());
// fflush(stdout);
int T=1,cs=0;
// cin >> T;
while(T--){
//cout << "Case " << ++cs << ": " ;
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11804kb
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: -100
Wrong Answer
time: 0ms
memory: 13872kb
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:
10
result:
wrong answer 1st numbers differ - expected: '100', found: '10'