fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int t;
  10.     cin >> t;
  11.     long long arr[500][500]; 
  12.     long long rowS[500], colS[500]; 
  13.  
  14.     while (t--) {
  15.         int n, m, k;
  16.         cin >> n >> m >> k;
  17.  
  18.         fill(begin(rowS), end(rowS), 0);
  19.         fill(begin(colS), end(colS), 0);
  20.  
  21.         for (int i = 0; i < n; i++) {
  22.             for (int j = 0; j < m; j++) {
  23.                 cin >> arr[i][j];
  24.                 rowS[i] += arr[i][j];
  25.                 colS[j] += arr[i][j];
  26.             }
  27.         }
  28.  
  29.  
  30.         long long ans = 0;
  31.  
  32.         if (n <= m) {
  33.             for (int mask = 0; mask < (1 << n); mask++) {
  34.                 if (__builtin_popcount(mask) > k) continue;
  35.  
  36.                 long long tmp = 0;
  37.                 priority_queue<long long> colValues;
  38.  
  39.                 for (int i = 0; i < n; i++) {
  40.                     if (mask & (1 << i)) {
  41.                         tmp += rowS[i];
  42.                     }
  43.                 }
  44.  
  45.                 for (int j = 0; j < m; j++) {
  46.                     long long overlap = 0;
  47.                     for (int i = 0; i < n; i++) {
  48.                         if (mask & (1 << i)) {
  49.                             overlap += arr[i][j];
  50.                         }
  51.                     }
  52.                     colValues.push(colS[j] - overlap);
  53.                 }
  54.  
  55.                 int takeFromCol = k - __builtin_popcount(mask);
  56.                 while (takeFromCol > 0 && !colValues.empty()) {
  57.                     long long maxValue = colValues.top();
  58.                     colValues.pop();
  59.                     if (maxValue > 0) {
  60.                         tmp += maxValue;
  61.                         takeFromCol--;
  62.                     }
  63.                 }
  64.                 ans = max(ans, tmp);
  65.             }
  66.         } else {
  67.             for (int mask = 0; mask < (1 << m); mask++) {
  68.                 if (__builtin_popcount(mask) > k) continue;
  69.  
  70.                 long long tmp = 0;
  71.                 priority_queue<long long> rowValues;
  72.  
  73.                 for (int i = 0; i < m; i++) {
  74.                     if (mask & (1 << i)) {
  75.                         tmp += colS[i];
  76.                     }
  77.                 }
  78.  
  79.                 for (int j = 0; j < n; j++) {
  80.                     long long overlap = 0;
  81.                     for (int i = 0; i < m; i++) {
  82.                         if (mask & (1 << i)) {
  83.                             overlap += arr[j][i];
  84.                         }
  85.                     }
  86.                     rowValues.push(rowS[j] - overlap);
  87.                 }
  88.  
  89.                 int takeFromRow = k - __builtin_popcount(mask);
  90.                 while (takeFromRow > 0 && !rowValues.empty()) {
  91.                     long long maxValue = rowValues.top();
  92.                     rowValues.pop();
  93.                     tmp += maxValue;
  94.                     takeFromRow--;
  95.                 }
  96.                 ans = max(ans, tmp);
  97.             }
  98.         }
  99.  
  100.         cout << ans << endl;
  101.     }
  102.  
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZLMCux
language:
C++ (gcc 8.3)
created:
59 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!