小度准备切一个蛋糕。这个蛋糕的大小为 N∗N，蛋糕每个部分的重量并不均匀。
小度一共可以切K 刀，每一刀都是垂直或者水平的，现在小度想知道在切了 K 刀之后，最重的一块蛋糕最轻的重量是多少。
格式
输入格式：
第1行包含N和K。其中：2≤
输入格式：
第1行包含N和K。其中：2≤N≤15，1≤K≤2N−2；
第2到第1+N行：每行 N 个数字，描述这一行蛋糕每个位置的重量 W。其中：0≤W≤1000。
≤15；
输出格式：
输出一个整数，最重的一块蛋糕最轻是多少。
样例 1
输入：
3 2
1 1 2
1 1 2
2 2 5
输出：
5
#include<bits/stdc++.h> using namespace std; int n,k,fal,max_; int a[20][20],sum[20][20],col[20],cnt[20],temp[20]; int get_sum(int x1,int y1,int x2,int y2){ return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; } bool check(int m){ if(m<max_) return false; for(int i=0;i<(1<<(n-1));i++){ fal=0; memset(col,0,sizeof(col)); memset(cnt,0,sizeof(cnt)); memset(temp,0,sizeof(temp)); vector<int> v; int count=0,ans=0,tmp=i; while(tmp){ count++; if(tmp&1){ v.push_back(count); ans++; } tmp/=2; } if(ans>k) continue; v.push_back(n); int p=0,top=1,down; for(int j=1;j<=n;j++){ p=0,top=1; for(int x:v){ down=x; int now=get_sum(top,j,down,j); if(now>m){ fal=1;break; } cnt[++p]+=now; if(col[j-1]){ cnt[p]=now; } temp[p]=now; if(cnt[p]>m){ col[j-1]=1; cnt[p]=now; for(int ii=1;ii<p;ii++) cnt[ii]=temp[ii]; } top=down+1; }if(fal) continue; for(int j=1;j<=n-1;j++){ if(ans<=k) return true; } return false; } } } int main( ) { cin>>n>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; max_=max(max_,a[i][j]); sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } int l=0,r=2000*15*15; while(l<=r){ int m=(l+r)>>1; if(check(m)) r=m-1; else l=m+1; }cout<<l<<'\n'; return 0; }
