module Main where
genarrs
:: Int -> [(Int, Int)] -- Generate all possible inner 1d intervalsgenarrs s = genarr 0 s
where
genarr _ 0 = []
genarr a b | a<=b = [(a,b)] ++ (genarr (a+1) b)
| a>b = genarr 0 (b-1)
cntoness
:: (Int,Int) -> [Int] -> Int -- Count ones in 1d interval inside 1d arraycntoness (a,b) xs | a > b = 0
| a <= b = (xs!!a) + cntoness ((a+1),b) xs -- Input array consists only of ones and zeros
-- so we can use sum for count.
cntonesa
:: ((Int,Int), (Int,Int)) -> [[Int]] -> Int -- Count ones in 2d interval inside 2d arraycntonesa (ab, (a,b)) xs | a > b = 0
| a <= b = (cntoness ab (xs!!a)) + cntonesa (ab, ((a+1),b)) xs
genarrs2d
:: Int -> Int -> [((Int, Int), (Int, Int))] -- Generate all possible inner 2d intervalsgenarrs2d a b = [(x, y) | x <- genarrs a, y <- genarrs b]
main = do
let w = nums!!0
let h = nums!!1
let n = nums!!2
let arr = readMatr w h
let cnts
= map (\x
-> fmap (cntonesa x
) arr
) (genarrs2d
(w
-1) (h
-1)) -- Coounts of ones in each array let fones
= fmap (\x
-> filter (==n
) x
) $ sequence cnts
-- Array with only counts equals n
bW9kdWxlIE1haW4gd2hlcmUKCmdlbmFycnMgOjogSW50IC0+IFsoSW50LCBJbnQpXSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gR2VuZXJhdGUgYWxsIHBvc3NpYmxlIGlubmVyIDFkIGludGVydmFscwpnZW5hcnJzIHMgPSBnZW5hcnIgMCBzCiAgICB3aGVyZQogICAgICAgIGdlbmFyciBfIDAgPSBbXQogICAgICAgIGdlbmFyciBhIGIgfCBhPD1iICA9IFsoYSxiKV0gKysgKGdlbmFyciAoYSsxKSBiKQogICAgICAgICAgICAgICAgICAgfCBhPmIgPSBnZW5hcnIgMCAoYi0xKQoKY250b25lc3MgOjogKEludCxJbnQpIC0+IFtJbnRdIC0+IEludAkJCQkJCSAgLS0gQ291bnQgb25lcyBpbiAxZCBpbnRlcnZhbCBpbnNpZGUgMWQgYXJyYXkKY250b25lc3MgKGEsYikgeHMgfCBhID4gYiA9IDAKICAgICAgICAgICAgICAgICAgfCBhID4gKGxlbmd0aCB4cykgfHwgYiA+IChsZW5ndGggeHMpID0gMAogICAgICAgICAgICAgICAgICB8IGEgPD0gYiA9ICh4cyEhYSkgKyBjbnRvbmVzcyAoKGErMSksYikgeHMgIC0tIElucHV0IGFycmF5IGNvbnNpc3RzIG9ubHkgb2Ygb25lcyBhbmQgemVyb3MKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAtLSBzbyB3ZSBjYW4gdXNlIHN1bSBmb3IgY291bnQuCgpjbnRvbmVzYSA6OiAoKEludCxJbnQpLCAoSW50LEludCkpIC0+IFtbSW50XV0gLT4gSW50CQkgIC0tIENvdW50IG9uZXMgaW4gMmQgaW50ZXJ2YWwgaW5zaWRlIDJkIGFycmF5CmNudG9uZXNhIChhYiwgKGEsYikpIHhzIHwgYSA+IGIgPSAwCiAgICAgICAgICAgICAgICAgICAgICAgIHwgYSA+IChsZW5ndGggeHMpIHx8IGIgPiAobGVuZ3RoIHhzKSA9IDAKICAgICAgICAgICAgICAgICAgICAgICAgfCBhIDw9IGIgPSAoY250b25lc3MgYWIgKHhzISFhKSkgKyBjbnRvbmVzYSAoYWIsICgoYSsxKSxiKSkgeHMKCmdlbmFycnMyZCA6OiBJbnQgLT4gSW50IC0+IFsoKEludCwgSW50KSwgKEludCwgSW50KSldICAgICAgICAgLS0gR2VuZXJhdGUgYWxsIHBvc3NpYmxlIGlubmVyIDJkIGludGVydmFscwpnZW5hcnJzMmQgYSBiID0gWyh4LCB5KSB8IHggPC0gZ2VuYXJycyBhLCB5IDwtIGdlbmFycnMgYl0KCnJlYWRNYXRyIDo6IEludCAtPiBJbnQgLT4gSU8gW1tJbnRdXQpyZWFkTWF0ciB3IGggPSBzZXF1ZW5jZSAuIHJlcGxpY2F0ZSBoICQgZm1hcCAobWFwIHJlYWQgLiB0YWtlIHcgLiB3b3JkcykgZ2V0TGluZQoKbWFpbiA6OiBJTyAoKQptYWluID0gZG8KICAgIHNpemVzbG4gPC0gZ2V0TGluZQogICAgbGV0IG51bXMgPSBtYXAgcmVhZCAkIHdvcmRzIHNpemVzbG4KICAgIGxldCB3ID0gbnVtcyEhMAogICAgbGV0IGggPSBudW1zISExCiAgICBsZXQgbiA9IG51bXMhITIKICAgIGxldCBhcnIgPSByZWFkTWF0ciB3IGgKICAgIGxldCBjbnRzID0gbWFwIChceCAtPiBmbWFwIChjbnRvbmVzYSB4KSBhcnIpIChnZW5hcnJzMmQgKHctMSkgKGgtMSkpIC0tIENvb3VudHMgb2Ygb25lcyBpbiBlYWNoIGFycmF5CiAgICBsZXQgZm9uZXMgPSBmbWFwIChceCAtPiBmaWx0ZXIgKD09bikgeCkgJCBzZXF1ZW5jZSBjbnRzICAgICAgICAgICAgICAtLSBBcnJheSB3aXRoIG9ubHkgY291bnRzIGVxdWFscyBuCiAgICBmbWFwIGxlbmd0aCBmb25lcyA+Pj0gcHJpbnQ=