QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523835#7051. Largest Common SubmatrixTahmid76WA 2ms13872kbC++143.0kb2024-08-18 19:27:402024-08-18 19:27:40

Judging History

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

  • [2024-08-18 19:27:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13872kb
  • [2024-08-18 19:27:40]
  • 提交

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;
}

詳細信息

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'