Submission #83572

#	Time	Username	Problem	Language	Result	Execution time	Memory
83572		ekrem	The Kingdom of JOIOI (JOI17_joioi)	C++98	0 / 100	3 ms	752 KiB

joioi

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define inf 1000000007
#define N 2005
using namespace std;

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

void cevir();
void cevir2();
void hazirla();

bool dene(int frk){
	int bas = 0, emn = inf, emx = 0, sumn = inf, sumx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= bas; j++){
			emn = min(emn, a[i][j]);
			emx = max(emx, a[i][j]);
		}
		for(; bas <= m; bas++){
			if((max(mx[i][bas+1],sumx)-min(mn[i][bas+1],sumn)<=frk) and (emx - emn <= frk) )
				break;
			if(bas == m)
				return 0;
			emn = min(emn, a[i][bas + 1]);
			emx = max(emx, a[i][bas + 1]);
		}
		sumx = max(sumx, mx[i][bas + 1]);
		sumn = min(sumn, mn[i][bas + 1]);
	}
	return 1;
}

void coz(){
	hazirla();
	int bas = 0;
	int son = inf;
	while(bas < son){
		if(dene(orta))
			son = orta;
		else
			bas = orta + 1;
	}
	// cout << orta << endl;
	ans = min(ans, orta);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%d",&a[i][j]);
	coz();
	// cout << dene(960387125) << endl;
	cevir();
	coz();
	cevir2();
	coz();
	// cout << dene(960387125) << endl;
	printf("%d\n", ans);
	return 0;
}

















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

void cevir2(){
	for(int i = 1; i <= n; i++)
		reverse(a[i] + 1, a[i] + m + 1);
}

void hazirla(){
	for(int i = 1; i <= n; i++){
		mn[i][m + 1] = inf;
		for(int j = m; j >= 1; j--){
			mn[i][j] = min(a[i][j], mn[i][j + 1]);
			mx[i][j] = max(a[i][j], mx[i][j + 1]);
		}
	}
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:55: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:58: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: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40