Submission #1072073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072073		LOLOLO	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	85 ms	17716 KiB

maxcomp

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

#define           s     second
#define           f     first
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e3 + 10;
int a[N][N], mx[N][N];
int n, m;

int cal() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            mx[i][j] = 2e9;
        }
    }

    int ans = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int v = a[i][j] - i - j;
            mx[i][j] = min({mx[i][j - 1], mx[i - 1][j], v});
            ans = max(ans, v - mx[i][j] - 1);   
        }
    }

    return ans;
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    int ans = cal();

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

    ans = max(ans, cal());

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

    ans = max(ans, cal());

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

    ans = max(ans, cal());
    cout << ans << '\n';
    return 0;
}

// a[x][y] - a[x1][y1] - (x - x1) - (y - y1)
// a[x][y] - a[x1][y1] - x + x1 - y + y1
// a[x][y] - x - y - (a[x1][y1] - x1 - y1)

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