Cod sursa(job #1077705)

Utilizator IoannaPandele Ioana Ioanna Data 11 ianuarie 2014 16:31:29
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#define NMAX 700

using namespace std;

int n, m, r, c;
int a[NMAX][NMAX];
int v[NMAX];
int maxim = 0;
char elim[7295];
int sum;

bool swapb = false;
int dim, celalalt, dim_v, dim_e;

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

void read() {

    in>>n>>m>>r>>c;
    if (n < m) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                in >> a[i][j];
            }
    } else {
        for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
            in >> a[j][i];
        swap(n,m);
        swap(r,c);
    }
}

void solutie() {
    sum = 0;
    for (int i = 0; i < m; i++) {
       v[i] = 0;
       for (int j = 0; j < n; j++) {
          if (elim[j]) continue;
          sum += a[j][i];
          v[i] += a[j][i];

        }
    }
    sort(v, v + m);
    int suma = sum;
    for (int j = 0; j < c; j++)
        suma -= v[j];
    if (suma > maxim) maxim = suma;

}


void backtracking(int k, int last) {
    if (k > r) {
        solutie();
        return;
    }

    for (int i = last + 1; i < n - (r - k); i++) {
        elim[i] = 1;
        backtracking(k + 1, i);
        elim[i] = 0;
  }
}

int main() {
    read();
    backtracking(1, -1);

    out<<maxim<<"\n";
    return 0;
}