Cod sursa(job #504475)

Utilizator andra23Laura Draghici andra23 Data 27 noiembrie 2010 20:14:25
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<fstream>
#include<algorithm>
#define maxn 1000

using namespace std;

short a[100][1000];
int col[maxn];
int s[20], v[20];
int maxim, m, n, r, c, contor;
ofstream g("elimin.out");

int solve() {
    int stotal = 0;
    for (int j = 1; j <= n; j++) {
        int s = 0;
        for (int k = 1; k <= m; k++) {
            if (v[k] == 0)
                s = s + a[k][j];
        }
        col[j] = s;
        stotal += s;
    }
    sort(col+1, col+n+1);
    for (int j = 1; j <= c; j++)
        stotal -= col[j];
    if (stotal > maxim)
        maxim = stotal;    
}

void back(int k) {
    for (int i = s[k-1]+1; i <= m; i++) {
        s[k] = i;
        v[i] = 1;
        if (k == r) {
            solve();    
        }
        else 
            back(k+1);
        v[i] = 0;
    }
}

int main() {
    ifstream f("elimin.in");
    
    
    f >> m >> n >> r >> c;
    
    int i, j, k;
    short x;
    if (m < n) {
        for (i = 1; i <= m; i++)
            for (j = 1; j <= n; j++)
                f >> a[i][j];
    }
    else {
        int aux = r;
        r = c;
        c = aux;
        for (i = 1; i <= m; i++) {
            for (j = 1; j <= n; j++) {
                f >> x;
                a[j][i] = x;    
            }    
        }
        aux = m;
        m = n;
        n = aux;
    }
    
    if (r == 0)
        solve();
    else 
        back(1);
    
    g << maxim << '\n';
       
    return 0;
}