Submission #715997

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
715997	2023-03-28T18:21:12 Z	vinnipuh01	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2583 ms	195888 KB

joioi

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int a[ 4 ][ 2001 ][ 2001 ], n, m;
int b[ 2001 ][ 2001 ];

bool ok( int x ) {
	for ( int t = 0; t < 4; t ++ ) {
		if ( t & 1 ) {
			mx = n;
			for ( int i = 1; i <= m; i ++ ) {
				for ( int j = 1; j <= n; j ++ )
					b[ i ][ j ] = 0;
			}
			for ( int i = 1; i <= m; i ++ ) {
				for ( int j = 1; j <= mx; j ++ ) {
					if ( a[ t ][ i ][ j ] > x ) {
						mx = j - 1;
						break;
					}
					b[ i ][ j ] = 1;
				}
			}
			int mnn = oo;
			int mxx = 0;
			for ( int i = 1; i <= m; i ++ ) {
				for ( int j = 1; j <= n; j ++ ) {
					if ( !b[ i ][ j ] ) {
						mxx = max( mxx, a[ t ][ i ][ j ] ) ;
						mnn = min( mnn, a[ t ][ i ][ j ] );
					}
				}
			}
			if ( mxx - mnn <= x )
				return true;	
		}
		else {
			mx = m;
			for ( int i = 1; i <= n; i ++ ) {
				for ( int j = 1; j <= m; j ++ )
					b[ i ][ j ] = 0;
			}
			for ( int i = 1; i <= n; i ++ ) {
				for ( int j = 1; j <= mx; j ++ ) {
					if ( a[ t ][ i ][ j ] > x ) {
						mx = j - 1;
						break;
					}
					b[ i ][ j ] = 1;
				}
			}
			int mnn = oo;
			int mxx = 0;
			for ( int i = 1; i <= n; i ++ ) {
				for ( int j = 1; j <= m; j ++ ) {
					if ( !b[ i ][ j ] ) {
						mxx = max( mxx, a[ t ][ i ][ j ] ) ;
						mnn = min( mnn, a[ t ][ i ][ j ] );
					}
				}
			}
			if ( mxx - mnn <= x )
				return true;
		}
	}
	return false;
}

main () {
	cin >> n >> m;
	mn = oo;
	for ( int i = 1; i <= n; i ++ ) {
		for ( int j = 1; j <= m; j ++ ) {
			cin >> a[ 0 ][ i ][ j ];
			mn = min( mn, a[ 0 ][ i ][ j ] );
		}
	}
	for ( int i = 1; i <= n; i ++ ) {
		for ( int j = 1; j <= m; j ++ )
			a[ 0 ][ i ][ j ] -= mn;
	}
	int x, y;
	x = y = 1;
	for ( int j = m; j >= 1; j -- ) {
		y = 1;
		for ( int i = 1; i <= n; i ++ ) {
			a[ 1 ][ x ][ y ] = a[ 0 ][ i ][ j ];
			y ++;
		}
		x ++;
	}
	x = 1;
	for ( int i = n; i >= 1; i -- ) {
		y = 1;
		for ( int j = m; j >= 1; j -- )
			a[ 2 ][ x ][ y ] = a[ 0 ][ i ][ j ], y ++;
		x ++;
	}
	x = 1;
	for ( int j = 1; j <= m; j ++ ) {
		y = 1;
		for ( int i = n; i >= 1; i -- )
			a[ 3 ][ x ][ y ] = a[ 0 ][ i ][ j ], y ++;
		x ++;
	}
//	for ( int t = 0; t < 4; t ++ ) {
//		cout << "----------\n";
//		for ( int i = 1; i <= n; i ++ ) {
//			for ( int j = 1; j <= m; j ++ )
//				cout << a[ t ][ i ][ j ] << " ";
//			cout << "\n";
//		}
//		cout << "----------\n";
//	}
	int l, r, mid;
	l = 0;
	r = 1e9;
	while ( r > l ) {
		mid = ( l + r ) / 2;
		if ( ok( mid ) )
			r = mid;
		else
			l = mid + 1;
	}
	cout << l;
}

Compilation message

joioi.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main () {
      | ^~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	440 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	436 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	440 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	436 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	440 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	436 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	440 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	436 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	2 ms	2900 KB	Output is correct
16	Correct	10 ms	5716 KB	Output is correct
17	Correct	22 ms	6168 KB	Output is correct
18	Correct	19 ms	6100 KB	Output is correct
19	Correct	20 ms	6100 KB	Output is correct
20	Correct	19 ms	5780 KB	Output is correct
21	Correct	25 ms	6264 KB	Output is correct
22	Correct	23 ms	6204 KB	Output is correct
23	Correct	22 ms	6220 KB	Output is correct
24	Correct	20 ms	5820 KB	Output is correct
25	Correct	25 ms	6268 KB	Output is correct
26	Correct	24 ms	6164 KB	Output is correct
27	Correct	23 ms	6228 KB	Output is correct
28	Correct	26 ms	6204 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	440 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	436 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	436 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	440 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	436 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	2 ms	2900 KB	Output is correct
16	Correct	10 ms	5716 KB	Output is correct
17	Correct	22 ms	6168 KB	Output is correct
18	Correct	19 ms	6100 KB	Output is correct
19	Correct	20 ms	6100 KB	Output is correct
20	Correct	19 ms	5780 KB	Output is correct
21	Correct	25 ms	6264 KB	Output is correct
22	Correct	23 ms	6204 KB	Output is correct
23	Correct	22 ms	6220 KB	Output is correct
24	Correct	20 ms	5820 KB	Output is correct
25	Correct	25 ms	6268 KB	Output is correct
26	Correct	24 ms	6164 KB	Output is correct
27	Correct	23 ms	6228 KB	Output is correct
28	Correct	26 ms	6204 KB	Output is correct
29	Correct	1769 ms	175904 KB	Output is correct
30	Correct	1696 ms	173900 KB	Output is correct
31	Correct	1779 ms	180052 KB	Output is correct
32	Correct	1771 ms	180032 KB	Output is correct
33	Correct	1367 ms	168788 KB	Output is correct
34	Correct	1766 ms	180164 KB	Output is correct
35	Correct	2583 ms	195848 KB	Output is correct
36	Correct	2117 ms	182432 KB	Output is correct
37	Correct	2551 ms	195888 KB	Output is correct