Submission #949941

#	Time	Username	Problem	Language	Result	Execution time	Memory
949941		starchan	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	872 ms	102104 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int SMX = 2e3+3;
int a[SMX][SMX];
int col[SMX][SMX];
bool check(int red, int n, int m)
{
	int l[n];
	int r[n];
	for(int i = 0; i < n; i++)
	{
		for(r[i] = 0; r[i] < m; r[i]++)
		{
			if(col[i][r[i]] == red)
				break;
		}
		for(int j = r[i]; j < m; j++)
		{
			if(col[i][j] == (3ll^red))
				return false;
		}
		r[i]--;
		l[i] = r[i];
		while((l[i] >= 0) && (col[i][l[i]] == 0))
			l[i]--;
	}
	int p = l[0];
	bool chad1 = false;
	for(int i = 1; i < n && !chad1; i++)
	{
		if(p > r[i])
		{
			chad1 = true;
			break;
		}
		p = max(p, l[i]);
	}
	int q = r[0];
	bool chad2 = false;
	for(int i = 1; i < n && !chad2; i++)
	{
		if(q < l[i])
		{
			chad2 = true;
			break;
		}
		q = min(q, r[i]);
	}
	if(chad1 && chad2)
		return false;
	return true;
}
signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	int mx, mn;
	mx = -INF; mn = INF;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			mx = max(mx, a[i][j]); mn = min(mn, a[i][j]);
		}
	} 
	int l = 0;
	int r = mx-mn;
	while(l < r)
	{
		int mid = (l+r)/2;
		bool fl = true;
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				col[i][j] = 0;
				if((mx-a[i][j]) > mid)
					col[i][j]+=1;
				if((a[i][j]-mn) > mid)
					col[i][j]+=2;
				if(col[i][j] == 3)
					fl = false;
			}
		}
		if(!fl)
		{
			l = mid+1;
			continue;
		}
		//can we seperate colors 1 and 2?
		bool works = check(1, n, m)||check(2, n, m);
		if(works)
			r = mid;
		else
			l = mid+1;
	}
	cout << l << "\n";
	return 0;
}

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