Submission #317512

#	Time	Username	Problem	Language	Result	Execution time	Memory
317512		casperwang	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	142 ms	17400 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int INF = 2e9;
int n, m;
int arr[MAXN+1][MAXN+1];
int pre[MAXN+1][MAXN+1];
int ans;

void rotate(int n, int m) {
  for (int i = 1; i <= max(n,m); i++)
    for (int j = i+1; j <= max(n,m); j++)
      swap(arr[i][j], arr[j][i]);
  for (int i = 1; i <= m; i++)
    for(int j = 1; j <= n/2; j++)
      swap(arr[i][j], arr[i][n-j+1]);
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      cin >> arr[i][j];
  for (int i = 0; i <= max(n,m); i++)
    pre[i][0] = INF;
  for (int i = 0; i <= max(n,m); i++)
    pre[0][i] = INF;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      pre[i][j] = min({pre[i-1][j], pre[i][j-1], arr[i][j]-i-j});
      ans = max({ans, arr[i][j]-i-j - pre[i-1][j], arr[i][j]-i-j - pre[i][j-1]});
    }
  }
  rotate(n, m);
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      pre[i][j] = min({pre[i-1][j], pre[i][j-1], arr[i][j]-i-j});
      ans = max({ans, arr[i][j]-i-j - pre[i-1][j], arr[i][j]-i-j - pre[i][j-1]});
    }
  }
  rotate(m, n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      pre[i][j] = min({pre[i-1][j], pre[i][j-1], arr[i][j]-i-j});
      ans = max({ans, arr[i][j]-i-j - pre[i-1][j], arr[i][j]-i-j - pre[i][j-1]});
    }
  }
  rotate(n, m);
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      pre[i][j] = min({pre[i-1][j], pre[i][j-1], arr[i][j]-i-j});
      ans = max({ans, arr[i][j]-i-j - pre[i-1][j], arr[i][j]-i-j - pre[i][j-1]});
    }
  }
  cout << ans-1 << "\n";
}

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