Cod sursa(job #2245370)

Utilizator vladisimovlad coneschi vladisimo Data 25 septembrie 2018 10:17:22
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <algorithm>
#include <cstdio>
#include <fstream>

int a[2 + 20][2 + 8200], sol = 0, sumCol[2 + 8200];

bool selected[2 + 20];

void backt(int n, int m, int r, int c, int k, int prev) {
  if (k > r) {
    int copy[2 + m];
    for (int j = 1; j <= m; j++)
      copy[j] = sumCol[j];
    std::sort(copy + 1, copy + m + 1);
    int sum = 0;
    for (int j = c + 1; j <= m; j++)
      sum += copy[j];
    sol = std::max(sum, sol);
  } else
    for (int i = prev + 1; i <= n; i++) {
      for (int j = 1; j <= m; j++)
        sumCol[j] -= a[i][j];
      backt(n, m, r, c, k + 1, 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, r, c;
  scanf("%d%d%d%d", &n, &m, &r, &c);
  bool swapping = false;
  if (m < n)
    swapping = true;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    if (swapping)
      scanf("%d", &a[j][i]);
    else
      scanf("%d", &a[i][j]);
  if (swapping) {
    std::swap(n, m);
    std::swap(r, c);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      sumCol[j] += a[i][j];
  backt(n, m, r, c, 1, 0);
  printf("%d", sol);
  return 0;
}