矩阵消除游戏

https://ac.nowcoder.com/acm/problem/200190

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 20;
int n,m,k,sum,ans;
int a[maxn][maxn],sh[maxn],sl[maxn];
int b[maxn];
int sone(int x){
    int cnt = 0;
    memset(b,0,sizeof(b));
    int i = 1;
    while(x){
        if(x & 1)
            b[i] = 1,cnt++;
        x >>= 1;
        i++;
    }
    return cnt;
}
bool cmp(int a,int b){
    return a > b;
}
signed main(){
    //freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            sh[i] += a[i][j];
        }
    }
    if(k >= n || k >= m){
        for(int i = 1; i <= n; i++)
            sum += sh[i];
        cout << sum << endl;
    }else {
        int tmp = (1 << n) - 1;
        for (int hang = 0; hang <= tmp; hang++) {
            sum = 0;
            int sn = sone(hang),sm = k - sn;
            if(sm < 0 || sm > m)
                continue;
            for(int i = 1; i <= n; i++){
                if(b[i])
                    sum += sh[i];
            }
            memset(sl,0,sizeof(sl));
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(!b[i])
                        sl[j] += a[i][j];
                }
            }
            //cout << sm << endl;
            sort(sl + 1,sl + m + 1,cmp);
            for(int i = 1; i<= sm; i++)
                sum += sl[i];
            ans = max(ans,sum);
        }
        cout << ans << endl;
    }
    return 0;
}