oj.uz

Submission #83572

# Submission time Handle Problem Language Result Execution time Memory
83572 2018-11-09T11:39:37 Z ekrem The Kingdom of JOIOI (JOI17_joioi) C++
0 / 100
 3 ms 752 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Incorrect 2 ms 752 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Incorrect 2 ms 752 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Incorrect 2 ms 752 KB Output isn't correct
13 Halted 0 ms 0 KB -