Submission #1177190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177190		nguyn	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	496 ms	16140 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 2e3 + 5;
const int inf = 1e9;

int a[N][N];
int n, m;
int maxCell;

bool check(int mid) {
	int last = m; 
	int mx = 0;
	int mn = inf; 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= last; j++) {
			if (maxCell - a[i][j] > mid) {
				last = j - 1;
				break;
			}
		}
		for (int j = last + 1; j <= m; j++) {
			mx = max(mx, a[i][j]);
			mn = min(mn, a[i][j]); 
		}
	}
	// cout << mid << '\n'; 
	// cout << mn << ' ' << mx << endl;
	if (mx - mn > mid) return 0;
	return 1;
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
    		cin >> a[i][j]; 
    		maxCell = max(maxCell, a[i][j]); 
    	}
    }
    int res = inf;
    for (int rotx = 0; rotx < 2; rotx++) {
    	for (int roty = 0; roty < 2; roty++) {
    		// for (int i = 1; i <= n; i++) {
    		// 	for (int j = 1; j <= m; j++) {
    		// 		cout << a[i][j] << ' ';
    		// 	}cout<< endl;
    		// }
    		int l = 0; 
    		int r = inf; 
    		while(l <= r) {
    			int mid = (l + r) / 2; 
    			if (check(mid)) {
    				// cout << mid << endl;
    				res = min(res, mid); 
    				r = mid - 1; 
    			}
    			else {
    				l = mid + 1; 
    			}
    		}
    		for (int i = 1; i <= n / 2; i++) {
				for (int j = 1; j <= m; j++) {
					swap(a[i][j], a[n - i + 1][j]); 
				}
			}
    	}
    	for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m / 2; j++) {
				swap(a[i][j], a[i][m - j + 1]); 
			}
		}
    }
    cout << res;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40