oj.uz

Submission #647170

# Submission time Handle Problem Language Result Execution time Memory
647170 2022-10-01T18:16:38 Z beaconmc The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,m;
ll grid[2001][2001];
ll grid2[2001][2001];

ll mx = -1;

ll minmaxl[2001][2001];
ll minmaxr[2001][2001];

void setup(){
	FOR(i,0,n){
		FOR(j,0,m){
			minmaxl[i][j] = 1000000000;
			minmaxr[i][j] = 1000000000;
		}
	}
	FORNEG(i,n-1,-1){
		minmaxl[i][0] = grid[i][0];
		FOR(j,1,m){
			minmaxl[i][j] = min(minmaxl[i][j-1], grid[i][j]);
		}
		if (i!=n-1){
			FOR(j,0,m){
				minmaxl[i][j] = min(minmaxl[i][j], minmaxl[i+1][j]);
			}
		}
	}

	FORNEG(i,n-1,-1){
		minmaxr[i][m-1] = grid[i][m-1];
		FORNEG(j,m-2,-1){
			minmaxr[i][j] = min(minmaxr[i][j+1], grid[i][j]);
		}
		if (i != n-1){
			FOR(j,m-1,-1){
				minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
			}
		}
	}
}

bool check(ll a){
	ll mini = 1000000000;
	ll maxi = -1;
	FOR(i,0,n){
		FOR(j,0,m){
			if (mx-minmaxl[i][j] > a){
            	mini = min(mini, grid[i][j]);
            	maxi = max(maxi, grid[i][j]);
			}
		}
	}
	if (maxi - mini <= a) return true;

	mini = 1000000000;
	maxi = -1;
	FOR(i,0,n){
		FOR(j,0,m){
			if (mx-minmaxr[i][j] > a){
            	mini = min(mini, grid[i][j]);
            	maxi = max(maxi, grid[i][j]);
			}
		}
	}
	if (maxi - mini <= a) return true;
	return false;

}
int main(){
	cin >> n >> m;
	FOR(i,0,n){
		FOR(j,0,m){
			cin >> grid[i][j];
			mx = max(mx, grid[i][j]);
			grid2[n-i-1][m-j-1] = grid[i][j];
		}
	}

	setup();
	ll lo = 0;
	ll hi = mx;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (check(mid)){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}
	ll ans = lo;
	FOR(i,0,n) FOR(j,0,m) grid[i][j] = grid2[i][j];

	setup();
	lo = 0;
	hi = mx;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (check(mid)){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}
	cout << min(ans,lo);



}

Compilation message

joioi.cpp: In function 'void setup()':
joioi.cpp:46:54: warning: array subscript -2 is below array bounds of 'll [2001]' {aka 'long long int [2001]'} [-Warray-bounds]
   46 |     minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
      |                                        ~~~~~~~~~~~~~~^
joioi.cpp:46:37: warning: array subscript -2 is below array bounds of 'll [2001]' {aka 'long long int [2001]'} [-Warray-bounds]
   46 |     minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
      |                         ~~~~~~~~~~~~^
joioi.cpp:46:54: warning: array subscript -2 is below array bounds of 'll [2001]' {aka 'long long int [2001]'} [-Warray-bounds]
   46 |     minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
      |                                        ~~~~~~~~~~~~~~^
joioi.cpp:46:37: warning: array subscript -2 is below array bounds of 'll [2001]' {aka 'long long int [2001]'} [-Warray-bounds]
   46 |     minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
      |                         ~~~~~~~~~~~~^
joioi.cpp:46:17: warning: array subscript -2 is below array bounds of 'll [2001]' {aka 'long long int [2001]'} [-Warray-bounds]
   46 |     minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
      |     ~~~~~~~~~~~~^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -