Submission #69610

#	Time	Username	Problem	Language	Result	Execution time	Memory
69610		MrTEK	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	1503 ms	263168 KiB

joioi

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 2e3 + 5;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;


int n,m,a[N][N],mn = INF,mx = -INF,ans;

void flip_row() {
	for (int i = 1 ; i <= n / 2 ; i++)
		for (int j = 1 ; j <= m ; j++)
			swap(a[i][j],a[n - i + 1][j]);
}

void flip_col() {
	for (int i = 1 ; i <= n ; i++)
		for (int j = 1 ; j <= m / 2 ; j++)
			swap(a[i][j],a[i][m - j + 1]);
}

bool check (int val) {

	int mxj = 1;
	for (int i = 1 ; i <= n; i++) {
		for (int j = 1 ; j <= m ; j++) {
			if (a[i][j] < mx - val)
				mxj = max(mxj,j + 1);
		}
		for (int j = 1 ; j <= m ; j++)
			if (a[i][j] > mn + val && mxj > j)
				return false; 
	}
	return true;
}

void print() {
	printf("\n\n\n");
	for (int i = 1 ; i <= n ; i++,puts(""))
		for (int j = 1 ; j <= m ; j++)
			printf("%d ",a[i][j]);
	printf("\n\n\n");
}

int solve() {
	int l = 0 , r = mx - mn;
	while (l < r) {
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main() {
	scanf("%d %d",&n,&m);
	for (int i = 1 ; i <= n ; i++)
		for (int j = 1 ; j <= m ; j++) {
			scanf("%d",&a[i][j]);
			mn = min(a[i][j],mn);
			mx = max(a[i][j],mx);
		}
	ans = solve();
	flip_row();
	// print();
	ans = min(ans,solve());
	flip_col();
	// print();
	ans = min(ans,solve());
	flip_row();
	// print();
	ans = min(ans,solve());
	printf("%d\n",ans);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
joioi.cpp:83:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

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