fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  5. #define ll long long
  6. #define ld double
  7. #define ii pair<int,int>
  8. #define se second
  9. #define fi first
  10. #define iii pair<int,ii>
  11. #define all(v) v.begin(),v.end()
  12. #define bit(x,i) (((x)>>(i))&1LL)
  13. #define flip(x,i) ((x)^(1LL<<(i)))
  14. #define ms(d,x) memset(d,x,sizeof(d))
  15. #define sitingfake 1
  16. #define orz 1
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22.  
  23. const ll mod = 1e9 + 7;
  24. const long long linf = 4557430888798830399;
  25. const int inf = 1061109567;
  26. const int maxarr = 1e6 + 5;
  27. int dx[] = {0 , -1 , 0 , 1};
  28. int dy[] = {-1 , 0 , 1 , 0};
  29.  
  30. template<typename T> bool maximize(T &a, const T &b)
  31. {
  32.     if(a < b) {a = b; return 1;}
  33.     return 0;
  34. }
  35.  
  36. template<typename T> bool minimize(T &a, const T &b)
  37. {
  38.     if(a > b) {a = b; return 1;}
  39.     return 0;
  40. }
  41.  
  42. inline void Plus(ll & a ,ll b)
  43. {
  44.     b %= mod;
  45.     a += b;
  46.     if(a >= mod) a -= mod;
  47.     if(a < 0) a += mod;
  48.     return;
  49. }
  50.  
  51. inline void Mul(ll & a, ll b)
  52. {
  53.     a %= mod; b %= mod;
  54.     a *= b;
  55.     a %= mod;
  56.     return;
  57. }
  58.  
  59. const int maxn = 1e3 + 7;
  60.  
  61. int a[maxn][5];
  62. int r , c , k;
  63. ll dp[2][maxn * 2][1 << 4];
  64. bool good[1 << 4];
  65. int sum[maxn][1 << 4];
  66.  
  67. void solve() {
  68.     cin >> r >> c >> k;
  69.     for (int i = 1; i <= r; i++)
  70.         for (int j = 1; j <= c; j++)
  71.             cin >> a[i][j];
  72.  
  73.     for (int i = 1; i <= r+1; i++) {
  74.         for (int mask = 0; mask < (1<<c); mask++) {
  75.             int s = 0;
  76.             for (int b = 0; b < c; b++)
  77.                 if (bit(mask, b)) s += a[i][b+1];
  78.             sum[i][mask] = s;
  79.         }
  80.     }
  81.  
  82.  
  83.     good[0] = 1;
  84.     for (int mask = 0; mask < (1<<c); mask++) if (good[mask]) {
  85.         for (int i = 0; i+1 < c; i++) {
  86.             if (!bit(mask,i) && !bit(mask,i+1))
  87.                 good[mask|(1<<i)|(1<<(i+1))] = 1;
  88.         }
  89.     }
  90.  
  91.  
  92.     static vector<array<int,4>> trans[1<<4];
  93.     for (int premask=0; premask<(1<<c); premask++) {
  94.         trans[premask].clear();
  95.         int base1 = ((1<<c)-1) ^ premask;
  96.         for (int curmask = base1; ; curmask = (curmask-1)&base1) {
  97.             if (good[curmask]) {
  98.                 int base2 = ((1<<c)-1) ^ curmask ^ premask;
  99.                 for (int nextmask = base2; ; nextmask = (nextmask-1)&base2) {
  100.                     if ((nextmask & curmask) == 0 && (nextmask & premask) == 0) {
  101.                         int used = (__builtin_popcount(curmask)/2) + __builtin_popcount(nextmask);
  102.                         trans[premask].push_back({curmask,nextmask,used,0});
  103.  
  104.                     }
  105.                     if (nextmask==0) break;
  106.                 }
  107.             }
  108.             if (curmask==0) break;
  109.         }
  110.     }
  111.  
  112.     static ll dp[2][1<<4][2005];
  113.     for (int i=0;i<2;i++) for (int m=0;m<(1<<c);m++) for (int n=0;n<=k;n++) dp[i][m][n]=-linf;
  114.     dp[1][0][0] = 0;
  115.  
  116.     for (int row=1; row<=r; row++) {
  117.         int cur=row&1, nxt=cur^1;
  118.         for (int m=0;m<(1<<c);m++) for (int n=0;n<=k;n++) dp[nxt][m][n]=-linf;
  119.         for (int need=0; need<=k; need++) {
  120.             for (int premask=0; premask<(1<<c); premask++) if (dp[cur][premask][need]>-linf) {
  121.                 for (auto [curmask,nextmask,used,_]: trans[premask]) {
  122.                     if (need+used>k) continue;
  123.                     int tmp = sum[row][curmask] + sum[row][nextmask] + sum[row+1][nextmask];
  124.                     maximize(dp[nxt][nextmask][need+used], dp[cur][premask][need]+tmp);
  125.                 }
  126.             }
  127.         }
  128.     }
  129.     cout << dp[(r+1)&1][0][k];
  130. }
  131.  
  132. signed main()
  133. {
  134.    ios_base::sync_with_stdio(0);
  135.    cin.tie(0);
  136.    cout.tie(0);
  137.  
  138.    #define task "domine"
  139.  
  140.    if(fopen(task".inp","r"))
  141.    {
  142.        freopen(task".inp","r",stdin);
  143.        freopen(task".out","w",stdout);
  144.    }
  145.  
  146.    int tc; tc = 1;
  147.  
  148.    while(tc--) solve();
  149.  
  150. }
  151.  
  152.  
  153.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5xGdQ4
language:
C++14 (clang 8.0)
created:
7 hours 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!