DMOPC '13 Contest 3 P4 - Snowman

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

Recently, a gigantic blizzard has hit Mizore's homeland. Because of this, she has lost electricity in her house. To pass the time, she decides to build a snowman with her friends. The snow lies in patches on the ground. However, not all the snow is pure, and Mizore does not want to contaminate her snowman with dirty snow.

To make a snowball, Mizore needs a continuous horizontal or vertical strip of snow which has the same length in patches as the snowball's size. After using a strip of snow to make a snowball, the snow from that strip is then used up, so one patch of snow may not be used to build two different snowballs. While avoiding the dirty snow, please help Mizore determine if she can make her snowman or not.

Input Specification

The first line of input will contain 3 integers: M, N, and S.

The next S lines will each contain a size of a snowball, B_i.

The next M lines will each contain N characters, the description of the ground. Each character will be either a 0 or a 10 is used to indicate clean snow, and 1 is used to indicate dirty snow.

Output Specification

On a single line, output yes if Mizore can build a snowman with only clean snow; otherwise, output no.


Test Case BatchMarksConstraints
1 [15 cases]201 \le M, N \le 4; 1 \le S \le 3; 1 \le B_i \le 4
2 [5 cases]251 \le M, N \le 5; 1 \le S \le 5; 1 \le B_i \le 5
3 [5 cases]251 \le M, N \le 10; 1 \le S \le 5; 1 \le B_i \le 10
4 [10 cases]301 \le M, N \le 10; 1 \le S \le 9; 1 \le B_i \le 10

Sample Input 1

3 4 3

Sample Output 1


Explanation for Sample Output 1

Mizore can use the snow like this to build all three snowballs (a being the smallest and c being the largest).


Sample Input 2

2 2 1

Sample Output 2


Explanation for Sample Output 2

No matter how Mizore assigns the pure snow, she cannot make a snowball of size 2, because the 2 patches of pure snow are connected neither horizontally nor vertically.


  • -1
    Dingledooper  commented on July 5, 2019, 4:25 p.m. edited

    Is there a way to not TLE? I'm using a brute force algorithm, but it seems to be too slow. Edit: figured it out

    • -1
      pblpbl  commented on Oct. 12, 2019, 12:50 p.m.

      Care to explain?