fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const int MAXR = 1002;
  7. const int MAXC = 4;
  8. const int MAXK = 2001;
  9. const ll INF = 1e10;
  10.  
  11. int r, c, k;
  12. ll dp[2][MAXK][1 << MAXC];
  13. int vis[2][MAXK][1 << MAXC];
  14. int a[MAXR][MAXC];
  15. int tot;
  16. int state[100][4];
  17. int cur[4];
  18. // 0: (0), 1: (1x2), 2: (2x1)
  19. vector<int> adj[1 << MAXC];
  20.  
  21.  
  22. void gen(int pos) {
  23.     if (pos == c) {
  24.         tot++;
  25.         memcpy(state[tot], cur, sizeof cur);
  26.         return;
  27.     }
  28.  
  29.     gen(pos + 1);
  30.     cur[pos] = 1;
  31.     gen(pos + 1);
  32.     if (pos + 1 < c) {
  33.         cur[pos] = 2;
  34.         gen(pos + 2);
  35.     }
  36.     cur[pos] = 0;
  37. }
  38.  
  39. void solve() {
  40.     cin >> r >> c >> k;
  41.     for (int i = 1; i <= r; i++) {
  42.         for (int j = 0; j < c; j++) {
  43.             cin >> a[i][j];
  44.         }
  45.     }
  46.  
  47.     gen(0);
  48.     for (int i = 1; i <= tot; i++) {
  49.         int smask = 0;
  50.         for (int j = 0; j < c; j++) {
  51.             if (state[i][j] == 1) {
  52.                 smask |= (1 << j);
  53.             }
  54.  
  55.             if (state[i][j] == 2) {
  56.                 smask |= (1 << j);
  57.                 smask |= (1 << j + 1);
  58.             }
  59.         }
  60.  
  61.         for (int mask = 0; mask < (1 << c); mask++) {
  62.             if (mask & smask) continue;
  63.             adj[mask].push_back(i);
  64.         }
  65.     }
  66.  
  67.     memset(dp, -0x3f, sizeof dp);
  68.     dp[1][0][0] = 0;
  69.  
  70.  
  71.     for (int i = 1; i <= r; i++) {
  72.         for (int j = 0; j <= k; j++) {
  73.             for (int mask = 0; mask < (1 << c); mask++) {
  74.                 if (dp[i & 1][j][mask] <= -INF) continue;
  75.  
  76.                 ll msum = 0;
  77.                 for (int b = 0; b < c; b++) {
  78.                     if (mask >> b & 1) {
  79.                         msum += a[i][b];
  80.                     }
  81.                 }
  82.  
  83.                 for (int st : adj[mask]) {
  84.                     int nmask = 0;  
  85.                     ll ssum = 0;  
  86.                     int scnt = 0;
  87.  
  88.                     for (int b = 0; b < c; b++) {
  89.                         if (state[st][b] == 1) {
  90.                             nmask |= (1 << b);           
  91.                             ssum += a[i][b];   
  92.                             scnt++;             
  93.                         } else if (state[st][b] == 2) { 
  94.                             ssum += a[i][b] + a[i][b + 1]; 
  95.                             scnt++;               
  96.                             b++; 
  97.                         }
  98.                     }
  99.  
  100.                     if (j + scnt <= k) {
  101.                         if (vis[i + 1 & 1][j + scnt][nmask] == i) {
  102.                             dp[i + 1 & 1][j + scnt][nmask] = max(dp[i + 1 & 1][j + scnt][nmask], dp[i & 1][j][mask] + msum + ssum);
  103.                         } else {
  104.                             vis[i + 1 & 1][j + scnt][nmask] = i;
  105.                             dp[i + 1 & 1][j + scnt][nmask] = dp[i & 1][j][mask] + msum + ssum;
  106.                         }
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.     }
  112.  
  113.     cout << dp[r + 1 & 1][k][0] << '\n';
  114. }
  115.  
  116. int main() {
  117.     ios_base::sync_with_stdio(false);
  118.     cin.tie(0);
  119.  
  120.     if (fopen("D:/elaina.inp", "r")) {
  121.         freopen("D:/elaina.inp", "r", stdin);
  122.         freopen("D:/elaina.out", "w", stdout);
  123.     }
  124.  
  125.     if (fopen("domine.inp", "r")) {
  126.         freopen("domine.inp", "r", stdin);
  127.         freopen("domine.out", "w", stdout);
  128.     }
  129.  
  130.     solve();
  131. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pgA9mA
language:
C++14 (gcc 8.3)
created:
2 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!