QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#735473#7051. Largest Common Submatrixgyydp123_LIMWA 0ms14188kbC++201.6kb2024-11-11 20:15:172024-11-11 20:15:19

Judging History

This is the latest submission verdict.

  • [2024-11-11 20:15:19]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 14188kb
  • [2024-11-11 20:15:17]
  • Submitted

answer

//Start: 2024-11-11 20:09:33
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1005;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,m,a[N][N],b[N][N];
pair<int,int>dl[N*N];
int l[N][N],r[N][N],u[N][N],d[N][N];
signed LJY(){
  n=read();m=read();
  For(i,1,n) For(j,1,m){
    a[i][j]=read();
    dl[a[i][j]].first+=i;
    dl[a[i][j]].second+=j;
  }For(i,1,n) For(j,1,m){
    b[i][j]=read();
    dl[b[i][j]].first-=i;
    dl[b[i][j]].second-=j;
  }
  For(i,1,n){
    l[i][1]=1;For(j,2,m) if(dl[a[i][j]]==dl[a[i][j-1]]) l[i][j]=l[i][j-1];else l[i][j]=j;
    r[i][m]=1;ForDown(j,m-1,1) if(dl[a[i][j]]==dl[a[i][j+1]]) r[i][j]=r[i][j+1];else r[i][j]=j;
  }For(i,1,m){
    u[1][i]=1;For(j,2,n) if(dl[a[j][i]]==dl[a[j-1][i]]) u[j][i]=u[j-1][i];else u[j][i]=j;
    d[i][n]=1;ForDown(j,n-1,1) if(dl[a[j][i]]==dl[a[j+1][i]]) d[j][i]=d[j+1][i];else d[j][i]=j;
  }int ans=0;
  For(i,1,n) For(j,1,m) if(l[i][j]==j)
    For(x,j,r[i][j]){
      int U=max(u[i][j],u[i][x]);
      int D=min(d[i][j],d[i][x]);
      ans=max(ans,(D-U+1)*(x-j+1));
    }printf("%d",ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14116kb

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: 14188kb

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:

0

result:

wrong answer 1st numbers differ - expected: '100', found: '0'