fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Task "MATRIX"
  5. #define N 2003
  6. #define ll long long
  7. #define INF 1000000000
  8. #define MOD 1000000007
  9.  
  10. int a[N][N], maxPre[N][N], maxSuf[N][N], dp[N][N];
  11.  
  12. int main() {
  13.     ios_base::sync_with_stdio(0);
  14.     cin.tie(0); cout.tie(0);
  15.     int m, n;
  16.     cin >> m >> n;
  17.     for (int i = 1; i <= m; i++)
  18.         for (int j = 1; j <= n; j++) cin >> a[i][j];
  19.  
  20.     for (int i = 1; i <= m; i++) {
  21.         int sum = 0, mi = 0;
  22.         for (int j = 1; j <= n; j++) {
  23.             sum += a[i][j];
  24.             maxPre[i][j] = max(0, sum - mi);
  25.             mi = min(mi, sum);
  26.         }
  27.     }
  28.  
  29.     for (int i = 1; i <= m; i++) {
  30.         int sum = 0, mi = 0;
  31.         for (int j = n; j >= 1; j--) {
  32.             sum += a[i][j];
  33.             maxSuf[i][j] = max(0, sum - mi);
  34.             mi = min(mi, sum);
  35.         }
  36.     }
  37.  
  38.     int sum = 0;
  39.     for (int i = 1; i <= m; i++) {
  40.         for (int j = 1; j <= n; j++) {
  41.             if (i == 1) {
  42.                 dp[i][j] = sum + a[i][j] + maxSuf[i][j + 1];
  43.                 sum += a[i][j];
  44.                 continue;
  45.             }
  46.             dp[i][j] = dp[i - 1][j] + a[i][j] + maxPre[i][j - 1] + maxSuf[i][j + 1];
  47.             sum = a[i][j];
  48.             for (int k = j - 1; k >= 1; k--) {
  49.                 sum += a[i][k];
  50.                 dp[i][j] = max(
  51.                     dp[i][j],
  52.                     dp[i - 1][k] + sum + maxPre[i][k - 1] + maxSuf[i][j + 1]
  53.                 );
  54.             }
  55.             sum = a[i][j];
  56.             for (int k = j + 1; k <= n; k++) {
  57.                 sum += a[i][k];
  58.                 dp[i][j] = max(
  59.                     dp[i][j],
  60.                     dp[i - 1][k] + sum + maxSuf[i][k + 1] + maxPre[i][j - 1]
  61.                 );
  62.             }
  63.         	if (i == m) ans = max(ans, dp[i][j]);
  64.         }
  65.     }
  66.     cout << dp[m][n];
  67.     return 0;
  68. }
  69.  
Time limit exceeded #stdin #stdout 5s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1we0co
language:
C++14 (gcc 8.3)
created:
337 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!