Cod sursa(job #2242627)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 19 septembrie 2018 08:44:38
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include <algorithm>

const int MAX_N = 100;
const int MAX_M = 10000;

int a[MAX_N][MAX_M], sumCol[MAX_M];

int cpy[MAX_M], answer = 0;

void get_answer(const int& k, const int& n, const int& m,
  const int& l, const int& c, const int& last) {

  if (k > l) {
    for (int i = 1; i <= m; i++)
      cpy[i] = sumCol[i];
    std::sort(cpy + 1, cpy + m + 1);
    int sum = 0;
    for (int i = c + 1; i <= m; i++)
      sum += cpy[i];
	answer = std::max(answer, sum);
  } else {
    for (int i = last + 1; i <= n; i++) {
	  for (int j = 1; j <= m; j++)
	    sumCol[j] -= a[i][j];
	  get_answer(k + 1, n, m, l, c, i);
	  for (int j = 1; j <= m; j++)
	    sumCol[j] += a[i][j];
    }
  }
}

int main() {

  freopen("elimin.in", "r", stdin);
  freopen("elimin.out", "w", stdout);

  int n, m, l, c;
  scanf("%d%d%d%d", &n, &m, &l, &c);
  bool reversed = false;
  if (n > m)
	reversed = true;
  for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++) {
	  if (!reversed)
	    scanf("%d", &a[i][j]);
	  else
	    scanf("%d", &a[j][i]);
	}
  std::swap(n, m);
  std::swap(l, c);
  for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++)
	  sumCol[j] += a[i][j];
  get_answer(1, n, m, l, c, 0);
  printf("%d\n", answer);

  fclose(stdin);
  fclose(stdout);

  return 0;
}