QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#711509	#7051. Largest Common Submatrix	Lcyanstars	WA	3ms	4308kb	C++14	1.8kb	2024-11-05 11:35:33	2024-11-05 11:35:33

Judging History

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

[2024-11-05 11:35:33]
评测

测评结果：WA
用时：3ms
内存：4308kb

查看

[2024-11-05 11:35:33]
提交

answer

#include <bits/stdc++.h>

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int main()
{   
    int n,m;
    scanf("%d%d",&n,&m);
    std::vector<std::vector<int> > A(n,std::vector<int>(m)),B(n,std::vector<int>(m));
    std::vector<int> idx(n*m+1);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            scanf("%d",&A[i][j]);
            idx[A[i][j]]=i*m+j;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&B[i][j]);
    std::vector<std::vector<int> > col(n,std::vector<int>(m));
    std::queue<int> q;
    int colc=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(col[i][j])
                continue;
            colc++;
            int x=idx[B[i][j]]/m,y=idx[B[i][j]]%m;
            q.push(0);
            while(!q.empty())
            {
                int di=q.front()/m,dj=q.front()%m;
                q.pop();
                col[i+di][j+dj]=colc;
                for(int k=0;k<4;k++)
                {
                    int ii=i+di+dx[k],jj=j+dj+dy[k];
                    int xx=x+di+dx[k],yy=y+dj+dy[k];
                    if(ii<0 || ii >= n || jj<0 || jj >= m || xx<0 || xx >= n || yy<0 || yy >= m || col[ii][jj] || B[ii][jj] != A[xx][yy])
                        continue;
                    q.push((di+dx[k])*m+(dj+dy[k]));
                }
            }
        }
    std::vector<std::vector<int> > l(n,std::vector<int>(m)),h(n,std::vector<int>(m));
    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(i && col[i-1][j] == col[i][j])
                l[i][j]=l[i-1][j]+1;
            if(j && col[i][j-1] == col[i][j])
                h[i][j]=h[i][j-1]+1;
            ans=std::max((l[i][j]+1)*(h[i][j]+1),ans);
        }
    printf("%d\n",ans);
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3880kb

input:

output:

result:

ok 1 number(s): "4"

Test #2:

score: 0

Accepted

time: 3ms

memory: 4308kb

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:

result:

ok 1 number(s): "100"

Test #3:

score: 0

Accepted

time: 2ms

memory: 3940kb

input:

10 10
6 48 98 83 7 56 22 49 61 34
8 87 91 100 16 17 86 24 9 23
94 50 81 59 51 21 52 20 33 25
73 1 70 45 36 31 88 90 12 69
64 57 60 5 85 29 37 96 92 41
89 67 79 84 35 68 46 18 38 63
27 55 65 95 11 43 47 72 80 66
75 39 58 62 77 53 15 40 3 71
32 82 10 99 44 2 30 76 74 28
19 78 13 97 26 42 54 14 4 93
6 ...

output:

result:

ok 1 number(s): "80"

Test #4:

score: -100

Wrong Answer

time: 2ms

memory: 4192kb

input:

10 10
37 16 29 24 14 20 41 63 4 15
71 99 17 26 33 47 83 55 89 52
32 22 95 44 81 93 78 31 42 12
94 70 25 46 18 97 57 62 68 67
21 69 54 27 13 96 64 48 59 28
11 49 9 73 100 90 85 36 2 58
74 53 98 34 7 5 3 91 23 76
77 86 84 92 50 51 45 61 30 66
35 1 10 79 39 6 80 82 43 88
75 60 38 87 40 8 19 56 72 65
37...

output:

result:

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