C++

#include <cstdio>

#include <cstring>

 

using namespace std;

 

int N,K,arr[20][20];

int first[20],sum[20];

int serch(int k,int m){

    memset(sum,0,sizeof(sum));

    int cnt=0;

    for(int j=1;j<=N;j++){

        int sum_2[20]={0,};

        for(int i=1;i<=N;i++){

            sum_2[first[i]]+=arr[j][i];

            if(sum_2[first[i]]>m)

                return 0;

        }

        for(int i=0;i<=k;i++){

            sum[i]+=sum_2[i];

            if(sum[i]>m){

                cnt++;

                for(int l=0;l<=k;l++){

                    sum[l]=sum_2[l];

                }

                if(cnt+k>K)

                    return 0;

                break;

            }

        }

    }

    return 1;

}

int case_(int i,int k,int m){

    first[i]=k;

    if(i==N||k==K){

        return serch(k,m);

    }

    if(case_(i+1,k,m))

       return 1;

    return case_(i+1,k+1,m);

}

 

int main()

{

    scanf("%d %d",&N,&K);

    for(int i=1;i<=N;i++){

        for(int j=1;j<=N;j++){

            scanf("%d",&arr[i][j]);

        }

    }

 

    int lb = 0, ub=1000 * N * N,mid;

    while(lb<ub){

        mid=(lb+ub)/2;

        if(case_(1,0,mid)){

            ub=mid;

        }else{

            lb=mid + 1;

        }

    }

    printf("%d",lb);

    return 0;

}