Advertisement
Josif_tepe

Untitled

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