fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll NEG = LLONG_MIN / 4;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int M, N;
  10.     if (!(cin >> M >> N)) return 0;
  11.     vector<vector<ll>> A(M + 1, vector<ll>(N + 2, 0));
  12.     for (int i = 1; i <= M; ++i)
  13.         for (int j = 1; j <= N; ++j)
  14.             cin >> A[i][j];
  15.  
  16.     vector<ll> dp(N + 2, NEG);
  17.  
  18.     vector<ll> left(N + 2, NEG), right(N + 2, NEG);
  19.     for (int j = 1; j <= N; ++j) {
  20.         if (j == 1) left[j] = A[1][j];
  21.         else left[j] = max(A[1][j], left[j-1] + A[1][j]);
  22.     }
  23.     for (int j = N; j >= 1; --j) {
  24.         if (j == N) right[j] = A[1][j];
  25.         else right[j] = max(A[1][j], right[j+1] + A[1][j]);
  26.     }
  27.     for (int j = 1; j <= N; ++j) dp[j] = max(left[j], right[j]);
  28.  
  29.     for (int i = 2; i <= M; ++i) {
  30.         vector<ll> temp(N + 2, NEG), L(N + 2, NEG), R(N + 2, NEG);
  31.  
  32.         for (int j = 1; j <= N; ++j) temp[j] = dp[j] + A[i][j];
  33.  
  34.         for (int j = 1; j <= N; ++j) {
  35.             if (j == 1) L[j] = temp[j];
  36.             else L[j] = max(temp[j], L[j-1] + A[i][j]);
  37.         }
  38.  
  39.         for (int j = N; j >= 1; --j) {
  40.             if (j == N) R[j] = temp[j];
  41.             else R[j] = max(temp[j], R[j+1] + A[i][j]);
  42.         }
  43.  
  44.         for (int j = 1; j <= N; ++j) dp[j] = max(L[j], R[j]);
  45.     }
  46.  
  47.     ll ans = NEG;
  48.     for (int j = 1; j <= N; ++j) ans = max(ans, dp[j]);
  49.     cout << ans << "\n";
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
2 3
1 2 3
4 -5 6
stdout
copy 
12
https://ideone.com/LM5ISV
language:
C++14 (gcc 8.3)
created:
4 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!