# 테페리넷

### 사이트 도구

ps:problems:boj:23318

# 행렬분할

ps
링크acmicpc.net/…
출처BOJ
문제 번호23318
문제명행렬분할
레벨골드 5
분류

파라메트릭 서치

시간복잡도O(2^m*nmlog(nmK))
인풋사이즈n<=20, m<=8, K<=15
사용한 언어Python
제출기록34576KB / 116ms
최고기록76ms
해결날짜2022/10/07

## 코드

"""Solution code for "BOJ 23318. 행렬분할".

Tags: [Parametric search]
"""

import itertools
import functools
from teflib import binsearch

INF = float('inf')

def can_divide(sum_limit, remaining_div_count, mat):
sums = [0] * (len(mat[0]))
for nums in mat:
sums = [s + n for s, n in zip(sums, nums)]
if any(s > sum_limit for s in sums):
if any(n > sum_limit for n in nums):
return False
sums = nums
remaining_div_count -= 1
if remaining_div_count < 0:
return False
return True

def main():
n, m = [int(x) for x in input().split()]
a, b = [int(x) for x in input().split()]
mat = [[int(x) for x in input().split()] for _ in range(n)]

all_sum = sum(sum(row) for row in mat)
for partition in itertools.combinations(range(1, m), b):
partition = (0, *partition, m)
new_mat = [[
sum(row[beg:end]) for beg, end in itertools.pairwise(partition)
] for row in mat]
pred = functools.partial(can_divide, remaining_div_count=a, mat=new_mat)
min_score = binsearch.minimum_valid_integer(0, all_sum, pred)
main()