oj.uz

Submission #146038

# Submission time Handle Problem Language Result Execution time Memory
146038 2019-08-21T16:30:52 Z AlexPop28 Maxcomp (info1cup18_maxcomp) C++11
100 / 100
 171 ms 21368 KB 
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

const int NMAX = 1000;

void Rotate(int &n, int &m, int a[NMAX][NMAX]) {
  static int b[NMAX][NMAX];
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      b[m - j - 1][i] = a[i][j];
    }
  }
  swap(n, m);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      a[i][j] = b[i][j];
    }
  }
}

bool uin(int &a, int &b) {
  return a > b ? (a = b, true) : false;
}

int Solve(int n, int m, const int a[NMAX][NMAX]) {
  int ans = -1;
  pair<pair<int, int>, pair<int, int>> per;
  static int minim[NMAX][NMAX];
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      minim[i][j] = a[i][j] - i - j;
      if (i != 0 && uin(minim[i][j], minim[i - 1][j])) {}
      if (j != 0 && uin(minim[i][j], minim[i][j - 1])) {}
      if (i != 0 && j != 0 && uin(minim[i][j], minim[i - 1][j - 1])) {}
      int curr = a[i][j] - i - j - minim[i][j] - 1;
      ans = max(ans, curr);
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int a[NMAX][NMAX];
  int n, m; cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
    }
  }
  int ans = -1;
  for (int i = 0; i < 4; ++i) {
    ans = max(ans, Solve(n, m, a));
    Rotate(n, m, a);
  }
  cout << ans << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12196 KB Output is correct
2 Correct 11 ms 12024 KB Output is correct
3 Correct 11 ms 12024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 11 ms 12196 KB Output is correct
10 Correct 11 ms 12024 KB Output is correct
11 Correct 11 ms 12024 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 3 ms 888 KB Output is correct
14 Correct 3 ms 1016 KB Output is correct
15 Correct 3 ms 1016 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 169 ms 20728 KB Output is correct
19 Correct 171 ms 20728 KB Output is correct
20 Correct 162 ms 20344 KB Output is correct
21 Correct 170 ms 20524 KB Output is correct
22 Correct 171 ms 20600 KB Output is correct
23 Correct 171 ms 20600 KB Output is correct
24 Correct 169 ms 21368 KB Output is correct