Cod sursa(job #2783112)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 13 octombrie 2021 19:39:44
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>

#define int short

#define pb push_back

using namespace std;

const int maxN = 7300;

int n, m, r, c;

int32_t maxSum;

int a[17][maxN + 5];

int st[maxN + 5];

int32_t s[maxN + 5];

void solve() {
  int32_t p = 1, sum = 0;
  for (int i = 1; i <= m; i++) {
    s[i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    if (p <= r && st[p] == i) {
      p++;
      continue;
    }
    for (int j = 1; j <= m; j++) {
      s[j] += a[i][j];
      sum += a[i][j];
    }
  }
  priority_queue<int32_t, vector<int32_t>, greater<int32_t>> pq;
  for (int i = 1; i <= m; i++) {
    pq.push(s[i]);
  }
  for (int i = 1; i <= c; i++) {
    sum -= pq.top();
    pq.pop();
  }
  maxSum = max(maxSum, sum);
}

void bkt(int p) {
  for (int i = st[p - 1] + 1; i <= n + p - r; i++) {
    st[p] = i;
    if (p == r) {
      solve();
    } else {
      bkt(p + 1);
    }
  }
}

int32_t main() {
  freopen("elimin.in", "r", stdin);
  freopen("elimin.out", "w", stdout);
  cin >> n >> m >> r >> c;
  if (n > m) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        cin >> a[j][i];
      }
    }
    swap(n, m);
    swap(r, c);
  } else {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
      }
    }
  }
  if (r != 0) {
    bkt(1);
  } else {
    solve();
  }
  cout << maxSum << "\n";
  return 0;
}