Cod sursa(job #504474)

Utilizator andra23Laura Draghici andra23 Data 27 noiembrie 2010 20:00:33
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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");

void back(int k) {
    for (int i = s[k-1]+1; i <= m; i++) {
        s[k] = i;
        v[i] = 1;
        if (k == r) {
            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;
        }
        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;
    }
    
    back(1);
    
    g << maxim << '\n';
       
    return 0;
}