Submission #282865

#	Time	Username	Problem	Language	Result	Execution time	Memory
282865		kshitij_sodani	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	158 ms	24696 KiB

maxcomp

//#pragma GCC optimize("Ofast,unroll-loops")//
//#pragma GCC target("fma,avx")//,avx2,fma")
//#pragma GCC optimization ("O3")


/*#pragma GCC optimization ("unroll-loops")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second


llo n,m;
llo it[1001][1001];
llo mi[1001][1001];
llo solve(){
	for(llo i=0;i<n+1;i++){
		for(llo j=0;j<m+1;j++){
			if(i==0 or j==0){
				mi[i][j]=1e18;
			}
			else{
				mi[i][j]=min(mi[i][j-1],mi[i-1][j]);
				mi[i][j]=min(it[i-1][j-1]-(i-1+j-1),mi[i][j]);
			}
		//	cout<<mi[i][j]<<":";
		}
		//cout<<endl;
	}


	llo kk=-1;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m;j++){
			kk=max(kk,it[i][j]-i-j-mi[i+1][j+1]-1);
		//	cout<<it[i][j]+i+j-mi[i+1][j+1]-1<<",,";
		}
		//cout<<endl;
	}
	//cout<<kk<<":"<<endl;
	return kk;




}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m;j++){
			cin>>it[i][j];
		}
	}
	llo ans=solve();
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m/2;j++){
			swap(it[i][j],it[i][m-j-1]);
		}
	}
	ans=max(ans,solve());
	for(llo i=0;i<n/2;i++){
		for(llo j=0;j<m;j++){
			swap(it[i][j],it[n-i-1][j]);
		}
	}
	ans=max(ans,solve());

	for(llo i=0;i<n;i++){
		for(llo j=0;j<m/2;j++){
			swap(it[i][j],it[i][m-j-1]);
		}
	}
	ans=max(ans,solve());
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m-1;j++){
			ans=max(ans,max(it[i][j],it[i][j+1])-min(it[i][j],it[i][j+1])-2);
		}
	}
	for(llo i=0;i<n-1;i++){
		for(llo j=0;j<m;j++){
			ans=max(ans,max(it[i][j],it[i+1][j])-min(it[i][j],it[i+1][j])-2);
		}
	}
	cout<<ans<<endl;




	return 0;
}

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