fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {   
  10.     freopen("wigz.in", "r", stdin);
  11.  
  12.     int t;
  13.     cin >> t;
  14.     int arr[500][500];
  15.     int rowS[500], colS[500];
  16.  
  17.     while (t--)
  18.     {
  19.         int n, m, k;
  20.         cin >> n >> m >> k;
  21.  
  22.         fill(begin(rowS), end(rowS), 0);
  23.         fill(begin(colS), end(colS), 0);
  24.  
  25.         for (int i = 0; i < n; i++)
  26.         {
  27.             for (int j = 0; j < m; j++)
  28.             {
  29.                 cin >> arr[i][j];
  30.                 rowS[i] += arr[i][j];
  31.                 colS[j] += arr[i][j];
  32.             }
  33.         }
  34.  
  35.         int ans = 0;
  36.  
  37.         if (n <= m)
  38.         {
  39.             for (int mask = 0; mask < (1 << n); mask++)
  40.             {
  41.                 if (__builtin_popcount(mask) > k)
  42.                     continue;
  43.  
  44.                 int tmp = 0;
  45.                 multiset<int> colValues;
  46.  
  47.                 for (int i = 0; i < n; i++)
  48.                 {
  49.                     if (mask & (1 << i))
  50.                     {
  51.                         tmp += rowS[i];
  52.                     }
  53.                 }
  54.  
  55.                 for (int j = 0; j < m; j++)
  56.                 {
  57.                     int overlap = 0;
  58.                     for (int i = 0; i < n; i++)
  59.                     {
  60.                         if (mask & (1 << i))
  61.                         {
  62.                             overlap += arr[i][j];
  63.                         }
  64.                     }
  65.                     colValues.insert(colS[j] - overlap);
  66.                 }
  67.  
  68.                 int takeFromCol = k - __builtin_popcount(mask);
  69.                 while (takeFromCol > 0 && !colValues.empty())
  70.                 {
  71.                     auto maxValue = prev(colValues.end());
  72.                     if (*maxValue > 0)
  73.                     {
  74.                         tmp += *maxValue;
  75.                         colValues.erase(maxValue); 
  76.                         takeFromCol--;
  77.                     }
  78.                     else
  79.                     {
  80.                         break; 
  81.                     }
  82.                 }
  83.                 ans = max(ans, tmp);
  84.             }
  85.         }
  86.         else
  87.         {
  88.             for (int mask = 0; mask < (1 << m); mask++)
  89.             {
  90.                 if (__builtin_popcount(mask) > k)
  91.                     continue;
  92.  
  93.                 int tmp = 0;
  94.                 multiset<int> rowValues;
  95.  
  96.                 for (int i = 0; i < m; i++)
  97.                 {
  98.                     if (mask & (1 << i))
  99.                     {
  100.                         tmp += colS[i];
  101.                     }
  102.                 }
  103.  
  104.                 for (int j = 0; j < n; j++)
  105.                 {
  106.                     int overlap = 0;
  107.                     for (int i = 0; i < m; i++)
  108.                     {
  109.                         if (mask & (1 << i))
  110.                         {
  111.                             overlap += arr[j][i];
  112.                         }
  113.                     }
  114.                     rowValues.insert(rowS[j] - overlap);
  115.                 }
  116.  
  117.                 int takeFromRow = k - __builtin_popcount(mask);
  118.                 while (takeFromRow > 0 && !rowValues.empty())
  119.                 {
  120.                     auto maxValue = prev(rowValues.end());
  121.                     tmp += *maxValue;
  122.                     rowValues.erase(maxValue); 
  123.                     takeFromRow--;
  124.                 }
  125.                 ans = max(ans, tmp);
  126.             }
  127.         }
  128.  
  129.         cout << ans << endl;
  130.     }
  131.  
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E7siTI
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!