Submission #146038

#	Time	Username	Problem	Language	Result	Execution time	Memory
146038		AlexPop28	Maxcomp (info1cup18_maxcomp)	C++11	100 / 100	171 ms	21368 KiB

maxcomp

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40