Submission #1171366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171366		lopkus	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	80 ms	16200 KiB

maxcomp

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int64_t>> a(n + 1, std::vector<int64_t>(m + 1));
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      std::cin >> a[i][j];
    }
  }
  int64_t ans = -1e18;
  /**
  for(int x = 1; x <= n; x++) {
    for(int y = 1; y <= m; y++) {
      for(int x1 = 1; x1 <= n; x1++) {
        for(int y1 = 1; y1 <= m; y1++) {
          int64_t cost = a[x][y] - a[x1][y1];
          int64_t path = x1 - x + y1 - y;
          ans = std::max(ans, cost - path);
        }
      }
    }
  }**/
  // x > x1 && y > y1
  // a[x][y] - a[x1][y1] - (x - x1 + y - y1)
  // a[x][y] - a[x1][y1] - x + x1 - y + y1
  std::vector<std::vector<int64_t>> dp(n + 2, std::vector<int64_t>(m + 2));
  for(int i = 0; i <= n + 1; i++) {
    for(int j = 0; j <= m + 1; j++) {
      dp[i][j] = -1e18;
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      dp[i][j] = std::max(dp[i][j], - a[i][j] + i + j - 1);
      ans = std::max(ans, a[i][j] - i - j + dp[i][j]);
    }
  }
  for(int i = 0; i <= n + 1; i++) {
    for(int j = 0; j <= m + 1; j++) {
      dp[i][j] = -1e18;
    }
  }
  // x > x1 && y < y1
  // a[x][y] - a[x1][y1] - (x - x1 + y1 - y)
  // a[x][y] - a[x1][y1] - x + x1 - y1 + y
  for(int j = m; j >= 1; j--) {
    for(int i = 1; i <= n; i++) {
      dp[i][j] = std::max(dp[i - 1][j], dp[i][j + 1]);
      dp[i][j] = std::max(dp[i][j], - a[i][j] + i - j - 1);
      ans = std::max(ans, a[i][j] - i + j + dp[i][j]);
    }
  }
  for(int i = 0; i <= n + 1; i++) {
    for(int j = 0; j <= m + 1; j++) {
      dp[i][j] = -1e18;
    }
  }
  // x < x1 && y > y1
  // a[x][y] - a[x1][y1] - (x1 - x + y - y1)
  // a[x][y] - a[x1][y1] - x1 + x - y + y1
  for(int j = 1; j <= m; j++) {
    for(int i = n; i >= 1; i--) {
      dp[i][j] = std::max(dp[i + 1][j], dp[i][j - 1]);
      dp[i][j] = std::max(dp[i][j], - a[i][j] - i + j - 1);
      ans = std::max(ans, a[i][j] + i - j + dp[i][j]);
    }
  }
  for(int i = 0; i <= n + 1; i++) {
    for(int j = 0; j <= m + 1; j++) {
      dp[i][j] = -1e18;
    }
  }
  // x < x1 && y < y1
  // a[x][y] - a[x1][y1] - (x1 - x + y1 - y)
  for(int j = m; j >= 1; j--) {
    for(int i = n; i >= 1; i--) {
      dp[i][j] = std::max(dp[i][j + 1], dp[i + 1][j]);
      dp[i][j] = std::max(dp[i][j], - a[i][j] - i - j - 1);
      ans = std::max(ans, a[i][j] + i + j + dp[i][j]);
    }
  }
  std::cout << ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40