QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751010#6746. Merge the RectanglesXfJbUhpyzgaW#AC ✓40ms39280kbC++141.1kb2024-11-15 16:43:242024-11-15 16:43:24

Judging History

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

  • [2024-11-15 16:43:24]
  • 评测
  • 测评结果:AC
  • 用时:40ms
  • 内存:39280kb
  • [2024-11-15 16:43:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
char s[1505];
int mp1[1505][1505],mp2[1505][1505],s1[1505][1505],s2[1505][1505];
int col[1505][1505],lx[1500*1500+5],ly[1500*1500+5];
int n,m;
bool dfs(int x1,int x2,int y1,int y2){
    int sum=0;
    for (int i=x1;i<x2;++i){
        if (s1[i][y2]-s1[i][y1-1]==y2-y1+1)
            return dfs(x1,i,y1,y2) && dfs(i+1,x2,y1,y2);
        sum+=s1[i][y2]-s1[i][y1-1];
    }
    for (int i=y1;i<y2;++i){
        if (s2[x2][i]-s2[x1-1][i]==x2-x1+1)
            return dfs(x1,x2,y1,i) && dfs(x1,x2,i+1,y2);
        sum+=s2[x2][i]-s2[x1-1][i];
    }
    return sum==0;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;++i){
        scanf("%s",s+1);
        for (int j=1;j<=m;++j){
            mp1[i][j]=s[j]-'0';
            s1[i][j]=s1[i][j-1]+mp1[i][j];
        }
    }
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        for (int j=1;j<m;++j){
            mp2[i][j]=s[j]-'0';
            s2[i][j]=s2[i-1][j]+mp2[i][j];
        }
    }
    puts(dfs(1,n,1,m)?"YES":"NO");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7932kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 2ms
memory: 9740kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 18ms
memory: 39168kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 26ms
memory: 39180kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 15ms
memory: 39096kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 15ms
memory: 38972kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: 0
Accepted
time: 15ms
memory: 39064kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #8:

score: 0
Accepted
time: 7ms
memory: 39092kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #9:

score: 0
Accepted
time: 18ms
memory: 39120kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #10:

score: 0
Accepted
time: 22ms
memory: 39204kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #11:

score: 0
Accepted
time: 18ms
memory: 39152kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #12:

score: 0
Accepted
time: 25ms
memory: 39228kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #13:

score: 0
Accepted
time: 14ms
memory: 39060kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #14:

score: 0
Accepted
time: 22ms
memory: 39280kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #15:

score: 0
Accepted
time: 25ms
memory: 39192kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #16:

score: 0
Accepted
time: 15ms
memory: 39192kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #17:

score: 0
Accepted
time: 23ms
memory: 39124kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #18:

score: 0
Accepted
time: 26ms
memory: 39008kb

input:

1500 1500
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #19:

score: 0
Accepted
time: 25ms
memory: 39244kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #20:

score: 0
Accepted
time: 18ms
memory: 38944kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #21:

score: 0
Accepted
time: 12ms
memory: 38920kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #22:

score: 0
Accepted
time: 29ms
memory: 39212kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #23:

score: 0
Accepted
time: 30ms
memory: 39268kb

input:

1500 1500
10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #24:

score: 0
Accepted
time: 19ms
memory: 39188kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #25:

score: 0
Accepted
time: 18ms
memory: 39120kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #26:

score: 0
Accepted
time: 25ms
memory: 39248kb

input:

1500 1500
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #27:

score: 0
Accepted
time: 34ms
memory: 39156kb

input:

1500 1500
11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #28:

score: 0
Accepted
time: 21ms
memory: 38960kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #29:

score: 0
Accepted
time: 20ms
memory: 39068kb

input:

1500 1500
00010000000000011110111101011011110011001110011110011101111011110111000111000110001101111011110101100011011110111101000011110111101110011110000001111011110111101111011100111100110000010110101111011110110000000001100011101111011000011001111011100110001111011110011101111011110111100000011110...

output:

YES

result:

ok answer is YES

Test #30:

score: 0
Accepted
time: 21ms
memory: 38964kb

input:

1500 1500
11100111101111011110000101000011110011101111001000001101111011110111000100011110110100101000000011001110000110111101110011110111101111011110111001000011110110001111001010110000011011110110001111010010111101111011110111000000001110111101111001010111000111000000110000000011000111000001011110...

output:

YES

result:

ok answer is YES

Test #31:

score: 0
Accepted
time: 20ms
memory: 38972kb

input:

1500 1500
11110111101111011110111101111001110000000111011110111101110011100111101101011000111100000000000111101111011110000001110000010111101000011100111101101001100110001111011110100001111011110101101110011000000001110011110111101110001100111101111011110000100000011010111101111011010111101110000000...

output:

YES

result:

ok answer is YES

Test #32:

score: 0
Accepted
time: 17ms
memory: 39116kb

input:

1500 1500
11100000000000000011100000000000000000000001110000000000000000000000000000000000000000000000001110000000000000000000000000001110000000000000000000011100000000111100000011100000011100000000000000000000000000000000000000000011100000000000000000000000001111000000000000000000000000000000000000...

output:

NO

result:

ok answer is NO

Test #33:

score: 0
Accepted
time: 24ms
memory: 39064kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #34:

score: 0
Accepted
time: 19ms
memory: 39188kb

input:

1500 1500
00011100000001111000000000000011111100000000000000000000000000000000111000000011100000000001110000111111000000000000000001111000000000000000011110000000000000000000000000000000000000111111001110000000000000001111000000000000000111000000000000000000000000000000111000000000000111000000000000...

output:

YES

result:

ok answer is YES

Test #35:

score: 0
Accepted
time: 11ms
memory: 39160kb

input:

1500 1500
00000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...

output:

NO

result:

ok answer is NO

Test #36:

score: 0
Accepted
time: 16ms
memory: 39128kb

input:

1500 1500
00000000011100111100000000000000000000000000000000000000000000000000000111000000000000001110001110000000000001111111101110000000000000000000001111000000011100000000000000000000000000000000000000000011100000111000000000000000001111000000000000000000000000000000000011111000000000000000000000...

output:

NO

result:

ok answer is NO

Test #37:

score: 0
Accepted
time: 24ms
memory: 39064kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000...

output:

YES

result:

ok answer is YES

Test #38:

score: 0
Accepted
time: 23ms
memory: 39160kb

input:

1500 1500
00001110000000000000000011100000000000000000000000000000000111100000000000001111000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000111000000000000000000000011100000000011100000000000000001110000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #39:

score: 0
Accepted
time: 12ms
memory: 38964kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO

result:

ok answer is NO

Test #40:

score: 0
Accepted
time: 7ms
memory: 39060kb

input:

1500 1500
00000000000000011100000000000000000000000000000000000000011100000011100000000000000011100011100000000000000000000000000000000000000000000000000000111000000001111000000000000000000000000000001111000001110000000000000000001110000000000000000000000000000000000000001111011100011100000000000000...

output:

NO

result:

ok answer is NO

Test #41:

score: 0
Accepted
time: 19ms
memory: 38912kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #42:

score: 0
Accepted
time: 22ms
memory: 39144kb

input:

1500 1500
00011100000001111111000001111111000011110000000111000000000000011100000000111000000000000000001111000000000000000000000000000000011111000011110000000000000111100000000000001110000000011100001111000000001111000000000001111011110000000000000000000000000000011110000000000000000000000001110000...

output:

YES

result:

ok answer is YES

Test #43:

score: 0
Accepted
time: 20ms
memory: 39184kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NO

result:

ok answer is NO

Test #44:

score: 0
Accepted
time: 24ms
memory: 39064kb

input:

1500 1500
00001110001110000011110000001111111000000000000111000001110000000000000000000000000000111000000000001110000000011111001111000000000000000000011110000000000111000000001111100000001111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...

output:

NO

result:

ok answer is NO

Test #45:

score: 0
Accepted
time: 23ms
memory: 39124kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #46:

score: 0
Accepted
time: 19ms
memory: 38980kb

input:

1500 1500
00000000000000000000000000000000000001110000000000000000000000000000001110000000000000011100000000000000000111100000000000000000001111000000011100000000000000111100000000000000001110000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #47:

score: 0
Accepted
time: 12ms
memory: 39176kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000001110000000000001110000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100...

output:

NO

result:

ok answer is NO

Test #48:

score: 0
Accepted
time: 13ms
memory: 39168kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #49:

score: 0
Accepted
time: 7ms
memory: 39164kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #50:

score: 0
Accepted
time: 12ms
memory: 26324kb

input:

750 1500
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #51:

score: 0
Accepted
time: 8ms
memory: 39080kb

input:

1500 750
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #52:

score: 0
Accepted
time: 12ms
memory: 25796kb

input:

750 1500
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #53:

score: 0
Accepted
time: 7ms
memory: 38960kb

input:

1500 750
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #54:

score: 0
Accepted
time: 28ms
memory: 38920kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #55:

score: 0
Accepted
time: 17ms
memory: 38980kb

input:

1500 1500
01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

YES

result:

ok answer is YES

Test #56:

score: 0
Accepted
time: 30ms
memory: 39060kb

input:

1500 1500
11111111111110110001100000101100100110111111010111111011000111100111111111101111111110011111111111110101111111111111011111111111111111111100001100000001011001011001100001111100110000000000111111111111111111111111111111111111110111111111111111111111111000111111111111000110000011111111100011...

output:

YES

result:

ok answer is YES

Test #57:

score: 0
Accepted
time: 40ms
memory: 39096kb

input:

1500 1500
01101111111000011111111111111111111110011110011101111110000111111001111111111111111111111111111101111011101101111110001101111100001111111111111111111111000001100000110111111111110011001101111111111011100001011111100111101100001111111111111111100001111111111111011111000111111111111111101110...

output:

YES

result:

ok answer is YES