Submission #197117

#	Time	Username	Problem	Language	Result	Execution time	Memory
197117		Redhood	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	173 ms	14604 KiB

maxcomp

#include<bits/stdc++.h>
#define rep(i,x) for(int i = 0; i < x; ++i)
using namespace std;

const int inf = 2e9;
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n , m;
    cin >> n >> m;
    vector <vector<int>> a(n,vector<int>(m));
    rep(i , n)
        rep(j , m)
            cin >> a[i][j];
    int answer = 0;
    vector<vector<int>>best;
    /// 1 zone

    best = vector<vector<int>>(n,vector<int>(m,inf));
    for(int i = 0; i < n; ++i){
        for(int j = m - 1; j >= 0; --j){
            if(i>0)best[i][j]=min(best[i][j],best[i-1][j]);
            if(j<m-1)best[i][j]=min(best[i][j],best[i][j+1]);
            best[i][j]=min(best[i][j],a[i][j]-i+j);
        }
    }

    rep(i,n)
        rep(j , m)
            answer = max(answer , a[i][j]-i+j-best[i][j]);
    /// 2 zone
    best = vector<vector<int>>(n,vector<int>(m,inf));
    for(int i = n-1; i >=0; --i){
        for(int j = m - 1; j >= 0; --j){
            if(i<n-1)best[i][j]=min(best[i][j],best[i+1][j]);
            if(j<m-1)best[i][j]=min(best[i][j],best[i][j+1]);
            best[i][j]=min(best[i][j],a[i][j]+i+j);
        }
    }
    rep(i,n)
        rep(j , m)
            answer = max(answer , a[i][j]+i+j-best[i][j]);
    /// 3 zone
    best = vector<vector<int>>(n,vector<int>(m,inf));
    for(int i = n-1; i >=0; --i){
        for(int j = 0; j < m; ++j){
            if(i<n-1)best[i][j]=min(best[i][j],best[i+1][j]);
            if(j>0)best[i][j]=min(best[i][j],best[i][j-1]);
            best[i][j]=min(best[i][j],a[i][j]+i-j);
        }
    }
    rep(i,n)
        rep(j , m)
            answer = max(answer , a[i][j]+i-j-best[i][j]);
    /// 4 zone
    best = vector<vector<int>>(n,vector<int>(m,inf));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(i>0)best[i][j]=min(best[i][j],best[i-1][j]);
            if(j>0)best[i][j]=min(best[i][j],best[i][j-1]);
            best[i][j]=min(best[i][j],a[i][j]-i-j);
        }
    }
    rep(i,n)
        rep(j , m)
            answer = max(answer , a[i][j]-i-j-best[i][j]);
    cout << answer - 1;
    return 0;
}

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