fork download
copy 
  1. #include             <bits/stdc++.h>
  2. #define fi           first
  3. #define se           second
  4. #define pii          pair<int, int>
  5. #define endl         "\n"
  6. #define FILE(A)      freopen(A".INP", "r", stdin); freopen(A".OUT", "w", stdout)
  7. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  8.  
  9. using namespace std;
  10. using ll = long long;
  11.  
  12. const int N    = 2207+2;
  13. const ll  INF  = 1e16  ;
  14.  
  15. int n, m, K;
  16. ll a[N][N];
  17. ll dp[2][N][N];
  18. pii id;
  19. auto &&f = dp[0];
  20. auto &&nxt = dp[1];
  21.  
  22. signed main(){
  23.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  24.     // FILE("garden");
  25.     cin >> n >> m >> K;
  26.     FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
  27.     FOR(i, 1, n) FOR(j, 1, m) dp[0][i][j] = -INF;
  28.     FOR(i, 1, n) dp[0][i][1] = a[i][1];
  29.     ll ans = -INF;
  30.     FOR(k, 0, K) {
  31.         FOR(j, 1, m) FOR(i, 1, n) {
  32.             // assume f[i][j] is best
  33.             f[i][j+1]   = max(f[i][j+1], f[i][j]+a[i][j+1]);
  34.             f[i-1][j+1] = max(f[i-1][j+1], f[i][j]+a[i-1][j+1]);
  35.             f[i+1][j+1] = max(f[i+1][j+1], f[i][j]+a[i+1][j+1]);
  36.         }
  37.         // calculate ans here
  38.         FOR(i, 1, n) ans = max(ans, f[i][m]);
  39.         // transition to dp[k + 1]
  40.         FOR(i, 1, n) FOR(j, 1, m) nxt[i][j] = -INF;
  41.         if(k < K) {
  42.             // iterate for each col
  43.             FOR(i, 1, n) {
  44.                 // for each row, I want to get the max cost and the second max cost
  45.                 id = {1, 2};
  46.                 if (f[i][id.fi] < f[i][id.se]) swap(id.fi, id.se);
  47.                 FOR(j, 3, m) {
  48.                     if (f[i][j] > f[i][id.fi]) id = {j, id.fi};
  49.                     else if (f[i][j] > f[i][id.se]) id.se = j;
  50.                 }
  51.                 FOR(j, 1, m) {
  52.                     if (j != id.fi) nxt[i][j] = max(nxt[i][j], f[i][id.fi] + a[i][j]);
  53.                     else nxt[i][j] = max(nxt[i][j], f[i][id.se] + a[i][j]);
  54.                 }
  55.             }
  56.             // iterate for each col
  57.             FOR(j, 1, m) {
  58.                 id = {1, 2};
  59.                 if (f[id.fi][j] < f[id.se][j]) swap(id.fi, id.se);
  60.                 FOR(i, 3, n) {
  61.                     if (f[i][j] > f[id.fi][j]) id = {i, id.fi};
  62.                     else if (f[i][j] > f[id.se][j]) id.se = i;
  63.                 }
  64.                 FOR(i, 1, n) {
  65.                     if (i != id.fi) nxt[i][j] = max(nxt[i][j], f[id.fi][j] + a[i][j]);
  66.                     else nxt[i][j] = max(nxt[i][j], f[id.se][j] + a[i][j]);
  67.                 }
  68.             }
  69.             // update current table to dp
  70.             FOR(i, 1, n) FOR(j, 1, m) f[i][j] = nxt[i][j];
  71.         }
  72.     }
  73.     cout << ans;
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-10000000000000000
https://ideone.com/WT95B1
language:
C++14 (clang 8.0)
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!