QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242277#7051. Largest Common SubmatrixAnwar#WA 0ms3600kbC++202.3kb2023-11-07 04:56:192023-11-07 04:56:19

Judging History

你现在查看的是最新测评结果

  • [2023-11-07 04:56:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3600kb
  • [2023-11-07 04:56:19]
  • 提交

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'