Cod sursa(job #2295696)

Utilizator TooHappyMarchitan Teodor TooHappy Data 3 decembrie 2018 21:21:37
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
 
using namespace std;

ifstream in("elimin.in");
ofstream out("elimin.out");

int m, n, r, c, table[1050][1050], rowsDeleted, colsDeleted, ans = -1e9;
bool col[1050], rows[1050];

void solve() {
    int sum = 0;

    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(!rows[i] && !col[j]) {
                sum += table[i][j];
            }
        }
    }

    ans = max(ans, sum);
}

void bkt() {
    if(rowsDeleted == r && colsDeleted == c) {
        solve();
        return;
    } else {
        for(int i = 1; i <= m; ++i) {
            if(!rows[i]) {
                rows[i] = true;
                rowsDeleted++;

                for(int j = 1; j <= n; ++j) {
                    if(!col[j]) {
                        col[j] = true;
                        colsDeleted++;
                        
                        bkt();
                        colsDeleted--;
                        col[j] = false;
                    }
                }
                rowsDeleted--;
                rows[i] = false;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    in >> m >> n >> r >> c;
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            in >> table[i][j];
        }
    }

    bkt();

    out << ans << "\n";

    in.close(); out.close();
 
    return 0;
}