oj.uz

Submission #891121

# Submission time Handle Problem Language Result Execution time Memory
891121 2023-12-22T08:06:19 Z thunopro Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 86 ms 29396 KB 
#include<bits/stdc++.h>
using namespace std ;
#define maxn 1009 
#define ll long long
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef vector<ll> vl ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ;  

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;} 
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow(a,n/2) ;
	if ( n % 2 ) return (1ll*res*res%mod*a%mod) ; 
	else return 1ll*res*res%mod ; 
}

int n , m ; 
int a [maxn][maxn] ;

int Min [maxn][maxn][4] ; 

void build () 
{
	memset ( Min , 0x3f , sizeof Min ) ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		for ( int j = 1 ; j <= m ; j ++ ) 
		{
			Min [i][j][0] = min (Min[i-1][j][0],Min[i][j-1][0]) ; 
			chkmin (Min[i][j][0],a[i][j]-i-j) ; 
		}
	}
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		for ( int j = m ; j >= 1 ; j -- ) 
		{
			Min [i][j][1] = min (Min[i-1][j][1],Min[i][j+1][1]) ; 
			chkmin (Min[i][j][1],a[i][j]-i+j) ; 
		}
	}
	for ( int i = n ; i >= 1 ; i -- ) 
	{
		for ( int j = 1 ; j <= m ; j ++ ) 
		{
			Min [i][j][2]  = min (Min[i+1][j][2],Min[i][j-1][2]) ; 
			chkmin (Min[i][j][2],a[i][j]+i-j) ; 
		}
	}
	for ( int i = n ; i >= 1 ; i -- ) 
	{
		for ( int j = m ; j >= 1 ; j -- ) 
		{
			Min [i][j][3] = min (Min[i+1][j][3],Min[i][j+1][3]) ; 
			chkmin (Min[i][j][3],a[i][j]+i+j) ; 
		}
	}
	
}
void solve () 
{
	int res = 0 ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		for ( int j = 1 ; j <= m ; j ++ ) 
		{
			int val = a [i][j] ; 
			// th1 
			chkmax (res,val-i-j-Min[i][j][0]) ; 
			// th2 
			chkmax (res,val-i+j-Min[i][j][1]) ; 
			// th3 
			chkmax (res,val+i-j-Min[i][j][2]) ; 
			// th4 
			chkmax (res,val+i+j-Min[i][j][3]) ; 
			
		}
	}
	cout << res - 1 ; 
}
int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 
	cin >> n >> m ; 
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) cin >> a [i][j] ; 
	
	build () ; 
	solve () ; 

}

Compilation message

maxcomp.cpp: In function 'void rf()':
maxcomp.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 17240 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 2 ms 17036 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16848 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 17240 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 2 ms 17036 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16984 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16860 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 2 ms 17060 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 17240 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 2 ms 17036 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 2 ms 16848 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16860 KB Output is correct
16 Correct 3 ms 16984 KB Output is correct
17 Correct 2 ms 17060 KB Output is correct
18 Correct 84 ms 28860 KB Output is correct
19 Correct 86 ms 28856 KB Output is correct
20 Correct 80 ms 28500 KB Output is correct
21 Correct 84 ms 28740 KB Output is correct
22 Correct 85 ms 28860 KB Output is correct
23 Correct 82 ms 28752 KB Output is correct
24 Correct 82 ms 29396 KB Output is correct