Submission #1126339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126339		I_love_Banu	Maxcomp (info1cup18_maxcomp)	C++20	30 / 100	23 ms	32072 KiB

maxcomp

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ld=long double;
using str=string;
template<class T,class U>using P=pair<T,U>;
using pi=P<int,int>;
template<class T>using V=vector<T>;
using vi=V<int>;
using vl=V<ll>;
using vvi=V<vi>;
using vpi=V<pair<int,int>>;
template<class T>int lwb(V<T>&a,T b){return int(lb(all(a),b)-begin(a));}
template<class T>int lwb(T a[],int n,T b){return int(lb(a,a+n,b)-a);}
template<class T>int upb(V<T>&a,T b){return int(ub(all(a),b)-begin(a));}
template<class T>int upb(T a[],int n,T b){return int(ub(a,a+n,b)-a);}
template<class T>ll sum(V<T>&a){return accumulate(all(a),0ll);}
template<class T>ll sum(T a[],int n){return accumulate(a,a+n,0ll);}
template<class T>T MAX(V<T>&a){return *max_element(all(a));}
template<class T>T MAX(T a[],int n){return *max_element(a,a+n);}
template<class T>T MIN(V<T>&a){return *min_element(all(a));}
template<class T>T MIN(T a[],int n){return *min_element(a,a+n);}
template<class T,class U>ifstream&operator>>(istream&in,P<T,U>a){return in>>a.first>>a.second;}
#define sz(x)int(size(x))
#define all(x)begin(x),end(x)
#define lla(x)rbegin(x),rend(x)
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
#define each(a,x)for(auto&a:x)
#define con const int

con mxN = 1e3 + 3;

ll A[mxN][mxN][2];
ll B[mxN][mxN][2];
ll a[mxN][mxN];

main(){
    int N, M;
    cin >> N >> M;

    F0R(i, N){
        F0R(j, M){
            cin >> a[i][j];
        }
    }

    memset(A, 0x3f, sizeof(A));
    memset(B, 0xc0, sizeof(B));

    ll ans = LLONG_MIN;
    F0R(i, N){
        F0R(j, M){
            A[i][j][0] = a[i][j] + 1;
            B[i][j][0] = a[i][j] - 1;
            if (0 < i){
                A[i][j][0] = min(A[i][j][0], A[i - 1][j][0] + 1);
                B[i][j][0] = max(B[i][j][0], B[i - 1][j][0] - 1);
            }
            if (0 < j){
                A[i][j][0] = min(A[i][j][0], A[i][j - 1][0] + 1);
                B[i][j][0] = max(B[i][j][0], B[i][j - 1][0] - 1);
            }
        }
        R0F(j, M){
            A[i][j][1] = a[i][j] + 1;
            B[i][j][1] = a[i][j] - 1;
            if (0 < i){
                A[i][j][1] = min(A[i][j][1], A[i - 1][j][0] + 1);
                B[i][j][1] = max(B[i][j][1], B[i - 1][j][0] - 1);
            }
            if (j < M - 1){
                A[i][j][1] = min(A[i][j][1], A[i][j + 1][0] + 1);
                B[i][j][1] = max(B[i][j][1], B[i][j + 1][0] - 1);
            }
        }
        F0R(j, M){
            ll mn = LLONG_MAX;
            if (0 < i){
                mn = min({mn, A[i - 1][j][0], A[i - 1][j][1]});
            }
            if (0 < j){
                mn = min(mn, A[i][j - 1][0]);
            }
            if (j < M - 1){
                mn = min(mn, A[i][j + 1][1]);
            }
            mn ++;
            ans = max(ans, a[i][j] - mn);
            ll mx = LLONG_MIN;
            if (0 < i){
                mx = max({mx, B[i - 1][j][0], B[i - 1][j][1]});
            }
            if (0 < j){
                mx = max(mx, B[i][j - 1][0]);
            }
            if (j < M - 1){
                mx = max(mx, B[i][j + 1][1]);
            }
            mx --;
            ans = max(ans, mx - a[i][j]);
        }
    }
    cout << ans << endl;
}

Compilation message (stderr)

maxcomp.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~

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