Submission #1319019

#TimeUsernameProblemLanguageResultExecution timeMemory
1319019m.zeeshanrashidMaxcomp (info1cup18_maxcomp)C++20
100 / 100
112 ms71420 KiB
// #ifdef __AVX2__
// #pragma GCC target "avx2"
// #endif
// #pragma GCC optimize "O3"
// #pragma GCC optimize "unroll-loops"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
using namespace std;
#define int long long
#define elif else if
#define all(l) begin(l),end(l)
#define rall(l) rbegin(l),rend(l)
#define append push_back
#define print(l) for(auto i:l) cout<<i<<' '; cout<<endl;
#define pprint(a,b) cout<<a<<' '<<b<<endl;
#define inp(l) for(auto &i:l) cin>>i;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pai make_pair
#define endl "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define vec vector

// const int mod=998244353;
const int mod1=998244353;
const int mod=1e9+7;
const int N=1e3+5;

int g[N][N];
int sr[2][N][N],pr[2][N][N],sc[2][N][N],pc[2][N][N];

int iter=1,itera=1;
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>g[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			pr[0][i][j]=max(pr[0][i][j-1]-1,g[i][j]);
			pc[0][i][j]=max(pc[0][i-1][j]-1,g[i][j]);
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			sr[0][i][j]=max(sr[0][i][j+1]-1,g[i][j]);
			sc[0][i][j]=max(sc[0][i+1][j]-1,g[i][j]);
		}
	}
	for(auto &i:pr[1]) for(auto &j:i) j=-1e18;
	for(auto &i:sr[1]) for(auto &j:i) j=-1e18;
	for(auto &i:pc[1]) for(auto &j:i) j=-1e18;
	for(auto &i:sc[1]) for(auto &j:i) j=-1e18;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			pr[1][i][j]=max(pr[1][i][j-1]-1,-g[i][j]);
			pc[1][i][j]=max(pc[1][i-1][j]-1,-g[i][j]);
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=m;j>=1;j--){
			sr[1][i][j]=max(sr[1][i][j+1]-1,-g[i][j]);
			sc[1][i][j]=max(sc[1][i+1][j]-1,-g[i][j]);
		}
	}
	int ans=-1e18;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			vec<int>a={pc[0][i][j],pr[0][i][j],sr[0][i][j],sc[0][i][j]};
			int ma=-1e18;
			for(auto k:a) ma=max(ma,k);
			int mi=-1e18;
			a={pc[1][i][j],pr[1][i][j],sr[1][i][j],sc[1][i][j]};
			for(auto k:a) mi=max(mi,k);
			ans=max(ans,ma+mi-1);
			// if(i==1 and j==2){
				// cout<<pc[1][i][j]<<' '<<pr[1][i][j]<<' '<<sr[1][i][j]<<' '<<sc[1][i][j]<<' '<<endl;
				// cout<<mi<<' '<<ma<<endl;
			// }
			// if(ma-mi-1==5){
				// cout<<i<<' '<<j<<endl;
				// cout<<mi<<endl;
			// }
		}
	}
	cout<<ans<<endl;
}
signed main(){
	// freopen("","r",stdin);
	// freopen("","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);
	cout<<fixed<<setprecision(20);
	// cin>>itera;
	for(iter=1;iter<=itera;iter++) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...