小度准备切一个蛋糕。这个蛋糕的大小为N ∗ N，蛋糕每个部分的重量并不均匀。小度一共可以切 K 刀，每一刀都是垂直或者水平的，现在小度想知道在切了 K 刀之后，最重的一块蛋糕最轻的重量是多少。

输入格式：
第1行包含N和K。其中：
2 ≤ N ≤ 15，1 ≤ K ≤ 2N − 2；
第2到第1 + N行：每行 N 个数字，描述这一行蛋糕每个位置的重量 W。其中：0 ≤ W ≤ 1000。

输出格式：
输出一个整数，最重的一块蛋糕最轻是多少

思路：个人认为还是比较困难的一个题目，其中二分和大范围枚举结合，非常头疼，同时还有一个非常重要的暴力思想，就是如何固定一个变量，对另一个变量操作，题解非常巧妙，用一个goto解决了我认为非常难以实现的操作，因为我在枚举的时候也发现，如果后面的出现竖着必须切一刀了，那么前面的都必须清空重新算，如果不用goto，可能就得用递归来实现。言归正传，这是一个二分加状态压缩的题目，我们枚举横着切的方式，然后再讨论竖着怎么切，如果一个地方必须切一刀，那么就把该行所有值全部重新算一遍，我通过L，R两个数组记录每次横切一块的L和R，当然也可以直接在下面的for里面计算，只是可能有点小小的难理解

#include <iostream>
#include <cstring>

using namespace std;
const int N = 20;
int a[N][N], L[N], R[N];
int sum[N], tot;
int n, k;

bool check(int x)
{
    for (int i = 0; i < 1 << (n - 1); i ++)
    {
        int idx = 0, p = 0;
        L[idx] = 0, R[idx] = 0;
        for (int j = 0; j < n - 1; j ++)
        {
            if (i >> j & 1) 
            {
                idx ++;
                L[idx] = R[idx - 1] + 1;
                R[idx] = R[idx - 1] + 1;
            }
            else R[idx] ++;
        }
        if (idx > k) continue;
        int cur = idx;
        for (int u = 0; u < n; u ++)
        {
            c:
            if (cur > k) break;
            for (int j = 0; j <= idx; j ++)
            {
                for (int k = L[j]; k <= R[j]; k ++)
                {
                    if (sum[j] + a[u][k] > x) 
                    {
                        cur ++;
                        memset(sum, 0, sizeof sum);
                        goto c;
                    }
                    else sum[j] += a[u][k];
                }
            }
        }
        if (cur <= k) return true;
    }
    return false;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++) 
        {
            cin >> a[i][j];
            tot += a[i][j];
        }

    int l = 0, r = tot;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}