Submission #1142555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142555		JelalTkm	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	127 ms	39936 KiB

maxcomp

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e3 + 1;
const int INF = 1e9 + 5000;
const int md = 1e9 + 7;

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 2, vector<int> (m + 2));
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        cin >> a[i][j];

    vector<vector<int>> mx1(n + 2, vector<int> (m + 2, -INF)), mn1(n + 2, vector<int> (m + 2, INF));
    vector<vector<int>> mx2(n + 2, vector<int> (m + 2, -INF)), mn2(n + 2, vector<int> (m + 2, INF));
    
    for (int j = 1; j <= m; j++)
      for (int i = 1; i <= n; i++) {
        mx1[i][j] = max({mx1[i - 1][j], mx1[i][j - 1], (a[i][j] + i + j)});
        mn1[i][j] = min({mn1[i - 1][j], mn1[i][j - 1], (a[i][j] - i - j)});
      }

    for (int j = m; j >= 1; j--)
      for (int i = 1; i <= n; i++) {
        mx2[i][j] = max({mx2[i - 1][j], mx2[i][j + 1], (a[i][j] + i - j)});
        mn2[i][j] = min({mn2[i - 1][j], mn2[i][j + 1], (a[i][j] - i + j)});
      }

    int ans = -1;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) {
        ans = max(ans, (a[i][j] - i - j) - mn1[i][j] - 1);
        ans = max(ans, mx1[i][j] - (a[i][j] + i + j) - 1);

        ans = max(ans, (a[i][j] - i + j) - mn2[i][j] - 1);
        ans = max(ans, mx2[i][j] - (a[i][j] + i - j) - 1);
      }

    cout << ans << '\n';
  }
  return 0;
}

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