oj.uz

Submission #317511

# Submission time Handle Problem Language Result Execution time Memory
317511 2020-10-30T00:38:38 Z casperwang Maxcomp (info1cup18_maxcomp) C++14
0 / 100
 9 ms 8192 KB 
#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]);
  if (n > m) return;
  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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -