AtCoder ABC159 E問題高速化の方法(貪欲法)

発生している問題・実現したいこと

AtCoder ABC159について、テストファイル19個のうち、8つがTLEとなりました。
プログラムを高速化し、ACするためにはどこを改善すれば良いでしょうか。

該当のソースコード

Python
1h,w,k = map(int,input().split())
2s = [list(map(int,input().strip())) for i in range(h)]
3
4def gru_hol(HOL): # セットから切り方を作る
5    groups_a = []
6    group_a = [0]
7    for i in range(h-1):
8        if(HOL[i] == 1):
9            groups_a.append(group_a)
10            group_a = [i+1]
11        else:
12            group_a.append(i+1)
13    groups_a.append(group_a)
14    return groups_a
15
16def nex_hol(HOL): #次のセットを作る
17    for j in range(h-1):
18        if(HOL[j] == 0):
19            HOL[j] = 1
20            for k in range(0,j):
21                HOL[k] = 0
22            break
23    return HOL
24
25def cutsum(grp,lscut,nxcut): #groupのlastcut~nextcutのホワイトチョコを数える
26    count = 0
27    for i in grp:
28        for j in range(lscut,nxcut):
29            count += s[i][j]
30    return count
31
32def cutcheck(grp_a,lscut_a): #切ってもダメかチェック
33    ct_a = 0
34    for i in grp_a:
35        ct_a += s[i][lscut_a]
36    if(ct_a > k):
37        return False
38    else:
39        return True
40
41min_cut = h + w - 2 #切り方の最小値　全部切ったらこの値
42hol = [0]*(h-1) #水平方向の切り方を2進数で表現
43for i in range(2**(h-1)):
44    fl_ag = 0
45    lastcut = 0
46    cuts = 0 #切る回数
47    groups = gru_hol(hol) #groupsを作る
48    for j in range(1,w): #鉛直方向のうちどこを切るか調べる
49        flag = 0
50        for group in groups:
51            if(cutsum(group,lastcut,j+1) > k):
52                if(cutcheck(group,lastcut) == False):
53                    fl_ag = 1 #切ってもダメなので、groupsから作り直し
54                    break
55                else:
56                    flag = 1 
57        if(fl_ag == 1):
58            break
59        if(flag == 1):
60            cuts += 1
61            lastcut = j
62
63    if(cutcheck(group,w-1) == True):
64        min_cut = min(min_cut,cuts+sum(hol))
65    nex_hol(hol)
66
67print(min_cut)