Cod sursa(job #1992215)

Utilizator DjokValeriu Motroi Djok Data 19 iunie 2017 21:26:40
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 4005;

int i, j, mask, n, m, r, c, rs, sum, v[N];

int main() {
  ifstream cin("elimin.in");
  ofstream cout("elimin.out");
  ios_base::sync_with_stdio(0);

  cin >> n >> m >> r >> c;

  int a[min(n, m)][max(m, n)];
  memset(a, 0, sizeof(a));

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

  for(mask = 0; mask < (1 << n); ++mask) {
    if(__builtin_popcount(mask) != r) continue;

    memset(v, 0, sizeof(v));

    for(i = 0; i < n; ++i) {
      if(mask & (1 << i)) continue;

      for(j = 0; j < m; ++j) v[j] += a[i][j];
    }

    sort(v, v + m);

    for(sum = 0, i = c; i < m; ++i) sum += v[i];

    rs = max(rs, sum);
  }

  cout << rs << '\n';

  return 0;
}