Guest User

e1

a guest
Sep 14th, 2019
265
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20.  
  21. using namespace std;
  22.  
  23. int n, m;
  24. vector<vector<int>> a;
  25.  
  26. vector<int> cm;
  27. vector<vector<int>> prec;
  28.  
  29. void init() {
  30.     prec.clear();
  31.     cm.clear();
  32.     cm.resize(m);
  33.     prec.resize(m, vector<int> (1 << n));
  34.     for (int i = 0; i < m; i++) {
  35.         for (int mask = 0; mask < (1 << n); mask++) {
  36.             for (int dl = 0; dl < n; dl++) {
  37.                 int cur = 0;
  38.                 for (int j = 0; j < n; j++) {
  39.                     if ((mask >> j) & 1) {
  40.                         cur += a[(dl + j) % n][i];
  41.                     }
  42.                 }
  43.                 prec[i][mask] = max(prec[i][mask], cur);
  44.             }
  45.         }
  46.     }
  47. }
  48.  
  49. int solve(vector<int> wr) {
  50.     int ans = 0;
  51.     for (int i = 0; i < n; i++) {
  52.         ans -= prec[wr[i]][cm[wr[i]]];
  53.         cm[wr[i]] |= (1 << i);
  54.         ans += prec[wr[i]][cm[wr[i]]];
  55.     }
  56.     for (int i = 0; i < n; i++) {
  57.         cm[wr[i]] = 0;
  58.     }
  59.     return ans;
  60. }
  61.  
  62. int ans = 0;
  63.  
  64. void gen(vector<int> &wr) {
  65.     if ((int)wr.size() == n) {
  66.         ans = max(ans, solve(wr));
  67.     } else {
  68.         for (int i = 0; i < m; i++) {
  69.             wr.push_back(i);
  70.             gen(wr);
  71.             wr.pop_back();
  72.         }
  73.     }
  74. }
  75.  
  76. void solve() {
  77.     a.clear();
  78.     ans = 0;
  79.     cin >> n >> m;
  80.     a.resize(n, vector<int> (m));
  81.     for (int i = 0; i < n; i++) {
  82.         for (int j = 0; j < m; j++) {
  83.             cin >> a[i][j];
  84.         }
  85.     }
  86.     init();
  87.     int mx = -1;
  88.     int mxj = -1;
  89.     for (int i = 0; i < n; i++) {
  90.         for (int j = 0; j < m; j++) {
  91.             if (mx < a[i][j]) {
  92.                 mx = a[i][j];
  93.                 mxj = j;
  94.             }
  95.         }
  96.     }
  97.     vector<int> wr = {mxj};
  98.     gen(wr);
  99.     cout << ans << '\n';
  100. }
  101.  
  102. signed main() {
  103.     ios_base::sync_with_stdio(false);
  104.     cin.tie(0);
  105.  
  106.     int q;
  107.     cin >> q;
  108.     while (q--) {
  109.         solve();
  110.     }
  111. }
RAW Paste Data