Cod sursa(job #504185)

Utilizator andra23Laura Draghici andra23 Data 26 noiembrie 2010 22:11:40
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<algorithm>
#define maxn 8000

using namespace std;

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

void rotateRight() {
    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= n; j++) 
            b[j][m-i+1] = a[i][j];
            
    int aux = m;
    m = n;
    n = aux;
    
    aux = r;
    r = c;
    c = aux; 
    
    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= n; j++) 
            a[i][j] = b[i][j];       
}

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;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            f >> a[i][j];
            
    if (n < m)
        rotateRight();
    back(1);
    
    g << maxim << '\n';
       
    return 0;
}