fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5. #define BIT(n) ((1ll) << (n))
  6. #define bit(mask, i) (((mask) >> (i)) & 1)
  7.  
  8. using namespace std;
  9.  
  10. const int maxn = 1e3;
  11. const int maxk = 2e3;
  12. const int maxc = 4;
  13. const ll INF = 1e18;
  14.  
  15. int n, m, k;
  16. ll dp[2][BIT(maxc) + 5][maxk + 10], a[maxn + 10][maxc + 10], sum[maxn + 10][BIT(maxc) + 5], ans = -INF;
  17. bool ok[BIT(maxc) + 5];
  18.  
  19. void maximize(ll &a, ll b)
  20. {
  21.     a = max(a, b);
  22. }
  23.  
  24. int main()
  25. {
  26.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  27.     if (fopen("DOMINE.INP", "r"))
  28.     {
  29.         freopen("DOMINE.INP", "r", stdin);
  30.         freopen("DOMINE.OUT", "w", stdout);
  31.     }
  32.  
  33.     cin >> n >> m >> k;
  34.     for (int i = 1; i <= n; i++)
  35.     {
  36.         for (int j = 0; j < m; j++)
  37.             cin >> a[i][j];
  38.         for (int mask = 0; mask < BIT(m); mask++)
  39.         {
  40.             for (int j = 0; j < m; j++)
  41.                 sum[i][mask] += bit(mask, j) * a[i][j];
  42.         }
  43.     }
  44.     for (int mask = 0; mask < BIT(m); mask++)
  45.     {
  46.         ok[mask] = 1;
  47.         for (int i = 0; i < m; i++)
  48.             if (bit(mask, i))
  49.             {
  50.                 if (bit(mask, i + 1))
  51.                     i++;
  52.                 else
  53.                 {
  54.                     ok[mask] = 0;
  55.                     break;
  56.                 }
  57.             }
  58.     }
  59.     for (int mask = 0; mask < BIT(m); mask++)
  60.         if (ok[mask])
  61.             dp[1][mask][__builtin_popcount(mask) / 2] = sum[1][mask];
  62.     for (int i = 1; i < n; i++)
  63.     {
  64.         for (int mask = 0; mask < BIT(m); mask++)
  65.             for (int cnt = 0; cnt <= k; cnt++)
  66.                 dp[i & 1 ^ 1][mask][cnt] = INF;
  67.         for (int mask = 0; mask < BIT(m); mask++)
  68.             for (int cnt = 0; cnt <= k; cnt++)
  69.             {
  70.                 if (dp[i & 1][mask][cnt] == INF)
  71.                     continue;
  72.                 int submask = (BIT(m) - 1) ^ mask;
  73.                 bool is_break_ = 0;
  74.                 for (int mask_col = submask; ; mask_col = (max(0, mask_col - 1)) & submask)
  75.                 {
  76.                     if (is_break_ && mask_col == 0)
  77.                         break;
  78.                     is_break_ = mask_col == 0;
  79.                     int submask_2 = (BIT(m) - 1) ^ mask_col;
  80.                     bool is_break = 0;
  81.                     for (int mask_row = submask_2; ; mask_row = (max(0, mask_row - 1)) & submask_2)
  82.                     {
  83.                         if (is_break && mask_row == 0)
  84.                             break;
  85.                         is_break = mask_row == 0;
  86.                         if (!ok[mask_row])
  87.                             continue;
  88.                         int next_cnt = cnt + __builtin_popcount(mask_col) + __builtin_popcount(mask_row) / 2;
  89.                         int next_mask = mask_col | mask_row;
  90.                         if (next_cnt > k)
  91.                             continue;
  92.                         ll s = dp[i & 1][mask][cnt] + sum[i][mask_col] + sum[i + 1][mask_row | mask_col];
  93.                         // cout << mask << ' ' << mask_col << ' ' << mask_row << ' ' << cnt << ' ' << next_cnt << ' ' << s, el;
  94.                         maximize(dp[i & 1 ^ 1][next_mask][next_cnt], s);
  95.                     }
  96.                 }
  97.             }
  98.     }
  99.     for (int mask = 0; mask < BIT(m); mask++)
  100.         maximize(ans, dp[n & 1][mask][k]);
  101.     cout << ans;
  102. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yWjRvk
language:
C++14 (gcc 8.3)
created:
1 day 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!