fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int n;
  10.     cin >> n;
  11.     if (n == 1) {
  12.         cout << 0 << endl;
  13.         return 0;
  14.     }
  15.     vector<vector<int>> grid(n, vector<int>(n));
  16.     for (int i = 0; i < n; i++) {
  17.         for (int j = 0; j < n; j++) {
  18.             cin >> grid[i][j];
  19.         }
  20.     }
  21.  
  22.     vector<vector<int>> prefix(n);
  23.     for (int j = 0; j < n; j++) {
  24.         prefix[j].resize(n);
  25.         prefix[j][0] = grid[0][j];
  26.         for (int i = 1; i < n; i++) {
  27.             prefix[j][i] = prefix[j][i-1] + grid[i][j];
  28.         }
  29.     }
  30.  
  31.     auto get_risk = [&](int col, int a, int b, int c) {
  32.         int low, high;
  33.         if (col == 0) {
  34.             low = b;
  35.             high = c;
  36.         } else if (col == n-1) {
  37.             low = b;
  38.             high = a;
  39.         } else {
  40.             low = b;
  41.             high = max(a, c);
  42.         }
  43.         if (high <= low) return 0;
  44.         int start = low;
  45.         int end = min(high - 1, n-1);
  46.         if (start > end) return 0;
  47.         int sum = prefix[col][end];
  48.         if (start > 0) sum -= prefix[col][start-1];
  49.         return sum;
  50.     };
  51.  
  52.     vector<vector<int>> dp(n+1, vector<int>(n+1, INT_MIN));
  53.     for (int a = 0; a <= n; a++) {
  54.         for (int b = 0; b <= n; b++) {
  55.             int risk = get_risk(0, 0, a, b);
  56.             dp[a][b] = risk;
  57.         }
  58.     }
  59.  
  60.     for (int j = 2; j < n; j++) {
  61.         vector<vector<int>> new_dp(n+1, vector<int>(n+1, INT_MIN));
  62.         for (int a = 0; a <= n; a++) {
  63.             for (int b = 0; b <= n; b++) {
  64.                 if (dp[a][b] == INT_MIN) continue;
  65.                 for (int c = 0; c <= n; c++) {
  66.                     int risk = get_risk(j-1, a, b, c);
  67.                     int total = dp[a][b] + risk;
  68.                     if (total > new_dp[b][c]) {
  69.                         new_dp[b][c] = total;
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.         dp = move(new_dp);
  75.     }
  76.  
  77.     int ans = 0;
  78.     for (int a = 0; a <= n; a++) {
  79.         for (int b = 0; b <= n; b++) {
  80.             if (dp[a][b] == INT_MIN) continue;
  81.             int risk = get_risk(n-1, a, b, 0);
  82.             int total = dp[a][b] + risk;
  83.             if (total > ans) ans = total;
  84.         }
  85.     }
  86.  
  87.     cout << ans << endl;
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
5
0 0 0 0 0
0 0 3 0 0
0 1 0 0 0
5 0 0 3 0
0 0 0 0 2
stdout
copy 
11
https://ideone.com/qGaEoC
language:
C++14 (gcc 8.3)
created:
6 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!