Submission #1319028

#TimeUsernameProblemLanguageResultExecution timeMemory
1319028Ghulam_JunaidMaxcomp (info1cup18_maxcomp)C++20
100 / 100
87 ms16308 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n, m, a[N][N], val[2][N][N], b[N][N];

int get(){
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            val[0][i][j] = val[1][i][j] = -2e9;
    for (int i = 1; i <= n; i ++)
        for (int j = m; j > 0; j --)
            val[0][i][j] = max(val[0][i][j + 1], -a[i][j] -j);
    for (int i = n; i > 0; i --)
        for (int j = 1; j <= m; j ++)
            val[1][i][j] = max(val[1][i + 1][j], a[i][j] -i);

    int ans = -1e9;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            ans = max(ans, val[0][i][j] + j + val[1][i][j] + i - 1);

    return ans;
}

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

int main(){
    ios::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 overall = -2e9;
    for (int i = 0; i < 4; i ++){
        overall = max(overall, get());
        rotate();
    }
    cout << overall << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...