QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242277 | #7051. Largest Common Submatrix | Anwar# | WA | 0ms | 3600kb | C++20 | 2.3kb | 2023-11-07 04:56:19 | 2023-11-07 04:56:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , MOD = 1e9 + 7;
int32_t main() {
cin.tie(0);cin.sync_with_stdio(0);
cout.tie(0);cout.sync_with_stdio(0);
int n ,m;
cin >> n >> m;
int r[n*m + 1 ] , d[n*m + 1] ;
int a[n][m] , b[n][m] ;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j] ;
if(j) r[ a[i][j-1] ] = a[i][j] ;
if(i) d[ a[i-1][j] ] = a[i][j] ;
}
}
int mr[n][m] , md[n][m] , mu[n][m] ;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> b[i][j] ;
}
mr[i][m-1] = 1;
for(int j = m-2 ; j >= 0; j--)
{
mr[i][j] = 1;
if( r[ b[i][j] ] == b[i][j+1] ) mr[i][j] += mr[i][j+1] ;
}
}
for(int j =0 ;j < n ;j++)
{
md[n-1][j] = 1;
mu[0][j] = 1;
for(int i= n-2 ; i >=0 ; i--)
{
md[i][j] = 1;
if( d[ b[i][j] ] == b[i+1][j] ) md[i][j] += md[i+1][j] ;
}
for(int i = 1 ; i < n; i++)
{
mu[i][j] = 1;
if( d[ b[i-1][j] ] == b[i][j] ) mu[i][j] += mu[i-1][j] ;
}
}
int ans = 1;
for(int j =0 ; j < m ;j++)
{
vector<int> nxt(n , n) ;
stack<int> st ;
for(int i = 0 ;i <n; i++)
{
while ( !st.empty() && mr[i][j] < mr[ st.top() ][j] )
{
nxt[ st.top() ] = i ;
st.pop() ;
}
st.push(i) ;
}
while (st.empty() ==0 ) st.pop() ;
for(int i = 0 ; i <n ;i++) nxt[i] = min( nxt[i] , i + md[i][j] );
for(int i = n-1 ; i >= 0 ; i--)
{
while ( !st.empty() && mr[i][j] < mr[ st.top() ][j] )
{
ans = max( ans , mr[st.top()][j] * ( nxt[st.top()] - max( i , st.top() -mu[st.top()][j] ) -1 ) ) ;
st.pop() ;
}
st.push(i) ;
}
while (st.empty() == 0)
{
ans = max( ans , mr[st.top()][j] * ( nxt[st.top()] - ( st.top() - mu[st.top()][j] ) - 1 ) ) ;
st.pop();
}
}
cout << ans ;
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3600kb
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:
32767
result:
wrong answer 1st numbers differ - expected: '4', found: '32767'