fork download
copy 
  1. // Author: 4uckd3v - Nguyen Cao Duc
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int MAX_M = 1000;
  8. const int MAX_N = 4;
  9. const int MAX_K = 2000;
  10. const int MOD = 1e9 + 7;
  11. const ll INF = 1e18;
  12.  
  13. template <class X, class Y>
  14. bool maximize(X& x, const Y& y) {
  15.     if (x >= y) return false;
  16.     x = y;
  17.     return true;
  18. };
  19.  
  20. int m, n, k;
  21. int a[MAX_M + 5][MAX_N + 5];
  22. int sum[MAX_M + 5][1 << MAX_N];
  23. ll nxt[MAX_K + 5][1 << MAX_N], cur[MAX_K + 5][1 << MAX_N];
  24.  
  25. bool offBit(int mask, int i) {
  26.     return !(mask >> i & 1);
  27. };
  28.  
  29. void baseCase() {
  30.     cur[0][0] = 0;
  31.     for (int i = 0; i < n; i++) {
  32.         if (i + 1 < n) cur[1][(1 << i) | (1 << (i + 1))] = a[1][i] + a[1][i + 1];
  33.     };
  34.     if (n == 4) cur[2][(1 << n) - 1] = sum[1][(1 << n) - 1];
  35. };
  36.  
  37. void transition(int i, int j, int mask) {
  38.     ll& curDp = cur[j][mask];
  39.     maximize(nxt[j][0], curDp);
  40.  
  41.     if (n >= 1) {
  42.         for (int p = 0; p < n; p++) {
  43.             if (offBit(mask, p)) maximize(nxt[j + 1][1 << p], curDp + a[i][p] + a[i + 1][p]);
  44.         };
  45.     };
  46.  
  47.     if (n >= 2) {
  48.         for (int p = 0; p + 1 < n; p++) {
  49.             int nextMask = (1 << p) | (1 << (p + 1));
  50.             // (2x1, 2x1)
  51.             if (j + 2 <= k && offBit(mask, p) && offBit(mask, p + 1))
  52.                 maximize(nxt[j + 2][nextMask], curDp + sum[i + 1][nextMask] + sum[i][nextMask]);
  53.  
  54.             // (1x2)
  55.             if (j + 1 <= k)
  56.                 maximize(nxt[j + 1][nextMask], curDp + sum[i + 1][nextMask]);
  57.         };
  58.     };
  59.     if (n >= 3) {
  60.         for (int p = 0; p < n; p++) {
  61.             // (2x1, 0, 2x1)
  62.             if (p + 2 < n && j + 2 <= k && offBit(mask, p) && offBit(mask, p + 2)) {
  63.                 int nextMask = (1 << p) | (1 << (p + 2));
  64.                 maximize(nxt[j + 2][nextMask], curDp + sum[i][nextMask] + sum[i + 1][nextMask]);
  65.             };
  66.             // (2x1, 2x1, 2x1)
  67.             if (p + 2 < n && j + 3 <= k && offBit(mask, p) && offBit(mask, p + 1) && offBit(mask, p + 2)) {
  68.                 int nextMask = (1 << p) | (1 << (p + 1)) | (1 << (p + 2));
  69.                 maximize(nxt[j + 3][nextMask], curDp + sum[i][nextMask] + sum[i + 1][nextMask]);
  70.             };
  71.             // (2x1, 1x2)
  72.             if (p + 2 < n && j + 2 <= k && offBit(mask, p)) {
  73.                 int nextMask = (1 << p) | (1 << (p + 1)) | (1 << (p + 2));
  74.                 maximize(nxt[j + 2][nextMask], curDp + a[i][p] + sum[i + 1][nextMask]);
  75.             };
  76.             // (1x2, 2x1)
  77.             if (p - 2 >= 0 && j + 2 <= k && offBit(mask, p)) {
  78.                 int nextMask = (1 << p) | (1 << (p - 1)) | (1 << (p - 2));
  79.                 maximize(nxt[j + 2][nextMask], curDp + a[i][p] + sum[i + 1][nextMask]);
  80.             };
  81.         };
  82.     };
  83.  
  84.     if (n == 4) {
  85.         // (2x1, 2x1, 2x1, 2x1)
  86.         if (mask == 0 && j + 4 <= k) {
  87.             int nextMask = (1 << n) - 1;
  88.             maximize(nxt[j + 4][nextMask], curDp + sum[i][nextMask] + sum[i + 1][nextMask]);
  89.         };
  90.  
  91.         // (1x2, 1x2)
  92.         if (j + 2 <= k) {
  93.             int nextMask = (1 << n) - 1;
  94.             maximize(nxt[j + 2][nextMask], curDp + sum[i + 1][nextMask]);
  95.         };
  96.         // (1x2, 2x1, 2x1)
  97.         if (j + 3 <= k && offBit(mask, 2) && offBit(mask, 3)) {
  98.             int nextMask = (1 << n) - 1;
  99.             maximize(nxt[j + 3][nextMask], curDp + a[i][2] + a[i][3] + sum[i + 1][nextMask]);
  100.         };
  101.         // (2x1, 2x1, 1x2)
  102.         if (j + 3 <= k && offBit(mask, 0) && offBit(mask, 1)) {
  103.             int nextMask = (1 << n) - 1;
  104.             maximize(nxt[j + 3][nextMask], curDp + a[i][0] + a[i][1] + sum[i + 1][nextMask]);
  105.         };
  106.         // (2x1, 1x2, 2x1)
  107.         if (j + 3 <= k && offBit(mask, 0) && offBit(mask, 3)) {
  108.             int nextMask = (1 << n) - 1;
  109.             maximize(nxt[j + 3][nextMask], curDp + a[i][0] + a[i][3] + sum[i + 1][nextMask]);
  110.         };
  111.  
  112.         for (int p = 0; p < n; p++) {
  113.             if (offBit(mask, p)) {
  114.                 // (2x1, 0, 0, 2x1)
  115.                 if (p + 3 < n && j + 2 <= k && offBit(mask, p + 3)) {
  116.                     int nextMask = (1 << p) | (1 << (p + 3));
  117.                     maximize(nxt[j + 2][nextMask], curDp + sum[i][nextMask] + sum[i + 1][nextMask]);
  118.                 };
  119.                 // (2x1, 2x1, 0, 2x1)
  120.                 if (p + 3 < n && j + 3 <= k && offBit(mask, p + 1) && offBit(mask, p + 3)) {
  121.                     int nextMask = (1 << p) | (1 << (p + 1)) | (1 << (p + 3));
  122.                     maximize(nxt[j + 3][nextMask], curDp + sum[i][nextMask] + sum[i + 1][nextMask]);
  123.                 };
  124.                 // (2x1, 0, 2x1, 2x1)
  125.                 if (p + 3 < n && j + 3 <= k && offBit(mask, p + 2) && offBit(mask, p + 3)) {
  126.                     int nextMask = (1 << p) | (1 << (p + 2)) | (1 << (p + 3));
  127.                     maximize(nxt[j + 3][nextMask], curDp + sum[i][nextMask] + sum[i + 1][nextMask]);
  128.                 };
  129.                 // (2x1, 0, 1x2)
  130.                 if (p + 3 < n && j + 2 <= k) {
  131.                     int nextMask = (1 << p) | (1 << (p + 2)) | (1 << (p + 3));
  132.                     maximize(nxt[j + 2][nextMask], curDp + a[i][p] + sum[i + 1][nextMask]);
  133.                 };
  134.                 // (1x2, 0, 2x1)
  135.                 if (p - 3 >= 0 && j + 2 <= k) {
  136.                     int nextMask = (1 << p) | (1 << (p - 2)) | (1 << (p - 3));
  137.                     maximize(nxt[j + 2][nextMask], curDp + a[i][p] + sum[i + 1][nextMask]);
  138.                 };
  139.             };
  140.         };
  141.     };
  142. };
  143.  
  144. int main() {
  145.     ios_base::sync_with_stdio(0);
  146.     cin.tie(0);
  147.     if (fopen("G.INP", "r")) {
  148.         freopen("G.INP", "r", stdin);
  149.         freopen("G.OUT", "w", stdout);
  150.     };
  151.     if (fopen("domine.INP", "r")) {
  152.         freopen("domine.INP", "r", stdin);
  153.         freopen("domine.OUT", "w", stdout);
  154.     };
  155.  
  156.     cin >> m >> n >> k;
  157.  
  158.     for (int i = 1; i <= m; i++) {
  159.         for (int j = 0; j < n; j++) {
  160.             cin >> a[i][j];
  161.         };
  162.  
  163.         for (int mask = 1; mask < (1 << n); mask++) {
  164.             int j = __builtin_ctz(mask);
  165.             sum[i][mask] = sum[i][mask ^ (1 << j)] + a[i][j];
  166.         };
  167.     };
  168.  
  169.     for (int i = 0; i <= m; i++) {
  170.         for (int j = 0; j <= k; j++) {
  171.             for (int mask = 0; mask < (1 << n); mask++) {
  172.                 cur[j][mask] = nxt[j][mask] = -INF;
  173.             };
  174.         };
  175.     };
  176.  
  177.     baseCase();
  178.     for (int i = 1; i < m; i++) {
  179.         for (int j = 0; j <= k; j++) {
  180.             for (int mask = 0; mask < (1 << n); mask++) {
  181.                 if (cur[j][mask] == -INF) continue;
  182.                 transition(i, j, mask);
  183.             };
  184.         };
  185.  
  186.         for (int j = 0; j <= k; j++) {
  187.             for (int mask = 0; mask < (1 << n); mask++) {
  188.                 cur[j][mask] = nxt[j][mask];
  189.                 nxt[j][mask] = -INF;
  190.             };
  191.         };
  192.     };
  193.  
  194.     ll res = -INF;
  195.     for (int mask = 0; mask < (1 << n); mask++) maximize(res, cur[k][mask]);
  196.  
  197.     cout << res << '\n';
  198. };
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/hif5gB
language:
C++14 (gcc 8.3)
created:
14 days 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!