Submission #636861

#	Time	Username	Problem	Language	Result	Execution time	Memory
636861		tvladm2009	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	427 ms	48228 KiB

maxcomp

#include <iostream>
#define int long long

using namespace std;

const int MAX_N = 1e3;
int a[MAX_N + 1][MAX_N + 1];
int dp1[MAX_N + 1][MAX_N + 1], dp2[MAX_N + 1][MAX_N + 1], dp3[MAX_N + 1][MAX_N + 1], dp4[MAX_N + 1][MAX_N + 1] ;
int n, m;

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp1[i][j] = i + j - a[i][j];
            if (i > 1) {
                dp1[i][j] = max(dp1[i][j], dp1[i - 1][j]);
            }
            if (j > 1) {
                dp1[i][j] = max(dp1[i][j], dp1[i][j - 1]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            dp2[i][j] = i - j - a[i][j];
            if (i > 1) {
                dp2[i][j] = max(dp2[i][j], dp2[i - 1][j]);
            }
            if (j < m) {
                dp2[i][j] = max(dp2[i][j], dp2[i][j + 1]);
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            dp3[i][j] = -i + j - a[i][j];
            if (i < n) {
                dp3[i][j] = max(dp3[i][j], dp3[i + 1][j]);
            }
            if (j > 1) {
                dp3[i][j] = max(dp3[i][j], dp3[i][j - 1]);
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 1; j--) {
            dp4[i][j] = -i - j - a[i][j];
            if (i < n) {
                dp4[i][j] = max(dp4[i][j], dp4[i + 1][j]);
            }
            if (j < m) {
                dp4[i][j] = max(dp4[i][j], dp4[i][j + 1]);
            }
        }
    }
    int answer = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            answer = max(answer, a[i][j] - i - j - 1 + dp1[i][j]);
            answer = max(answer, a[i][j] - i + j - 1 + dp2[i][j]);
            answer = max(answer, a[i][j] + i - j - 1 + dp3[i][j]);
            answer = max(answer, a[i][j] + i + j - 1 + dp4[i][j]);
        }
    }
    cout << answer;
    return 0;
}

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