Submission #1107946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107946		HasanV11010238	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	298 ms	32656 KiB

maxcomp

#include <bits/stdc++.h>
#define ll long long
#define INF 10000000000
using namespace std;
int n, m;
ll ans = -INF;
vector<vector<ll>> v;
void f(){
    vector<vector<ll>> mi(n + 1, vector<ll>(m + 1, INF));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            mi[i][j] = min(mi[i][j - 1] + 1, v[i][j]);
        }
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, INF));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            dp[i][j] = min(dp[i - 1][j] + 1, mi[i][j]);
            ans = max(ans, abs(v[i][j] - dp[i][j]) - 1);
        }
    }
}
void swv(){
    for(int i = 1; i <= n / 2; i++){
        swap(v[i], v[n - i + 1]);
    }
}
void swh(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m / 2; j++){
            swap(v[i][j], v[i][m - j + 1]);
        }
    }
}
int main(){
    cin>>n>>m;
    v.assign(n + 1, vector<ll>(m + 1, 0));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin>>v[i][j];
        }
    }
    f();
    swh();
    f();
    swv();
    f();
    swh();
    f();
    cout<<ans;
}

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