Advertisement
Josif_tepe

Untitled

Mar 16th, 2024
425
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1005;
  4. int n, m, k;
  5. int mat[maxn][maxn];
  6. int dp[1 << 5][maxn];
  7. int rec(vector<int> rows, int bitmask, int at) {
  8.     if(dp[bitmask][at] != -1) {
  9.         return dp[bitmask][at];
  10.     }
  11.     int res = 0;
  12.    
  13.     for(int i = at + 1; i < m; i++) {
  14.         bool ok = true;
  15.         int sum = 0;
  16.         for(int j = 0; j < rows.size(); j++) {
  17.             if(mat[rows[j]][at] > mat[rows[j]][i]) {
  18.                 ok = false;
  19.                 break;
  20.             }
  21.             sum += mat[rows[j]][i];
  22.         }
  23.         if(ok) {
  24.             res = max(res, rec(rows, bitmask,  i) + sum);
  25.         }
  26.     }
  27.     return dp[bitmask][at] = res;
  28. }
  29. int main() {
  30.     ios_base::sync_with_stdio(false);
  31.     cin >> n >> m >> k;
  32.     for(int i = 0; i < n; i++) {
  33.         for(int j = 0; j < m; j++) {
  34.             cin >> mat[i][j];
  35.         }
  36.     }
  37.     int res = 0;
  38.     vector<int> v;
  39.     memset(dp, -1, sizeof dp);
  40.     for(int bitmask = 0; bitmask < (1 << n); bitmask++) {
  41.         if(__builtin_popcount(bitmask) == k) {
  42.             vector<int> rows;
  43.             for(int i = 0; i < n; i++) {
  44.                 if(bitmask & (1 << i)) {
  45.                     rows.push_back(i);
  46.                 }
  47.             }
  48.  
  49.             for(int i = 0; i < m; i++) {
  50.                 int sum = 0;
  51.                 for(int j = 0; j < rows.size(); j++) {
  52.                     sum += mat[rows[j]][i];
  53.                 }
  54.                 int tmp_res = rec(rows, bitmask,  i) + sum;
  55.                 if(tmp_res > res) {
  56.                     res = tmp_res;
  57.                     v = rows;
  58.                 }
  59.                 else if(tmp_res == res) {
  60.                     v = min(v, rows);
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     cout << res << endl;
  66.     for(int i = 0; i < v.size(); i++) {
  67.         cout << v[i] + 1 << " ";
  68.     }
  69.      
  70.     return 0;
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement