Submission #378251

#	Time	Username	Problem	Language	Result	Execution time	Memory
378251		peijar	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	594 ms	101884 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000;
const int MAXROT = 4;

int altitude[MAXROT][MAXN][MAXN];
int nbLig, nbCol;
int petit(1e9), grand(0);

bool isOk(int iRot, int deltaMax)
{
	int prv(nbCol-1);
	for (int iLig(0); iLig < nbLig; ++iLig)
	{
		int curCol(-1);
		while (curCol + 1 <= prv and altitude[iRot][iLig][curCol+1] <= petit + deltaMax)
			++curCol;
		prv = curCol;
		if (prv == -1 and !iLig)
			return false;
		for (int iCol=curCol+1; iCol < nbCol; ++iCol)
			if (altitude[iRot][iLig][iCol] < grand - deltaMax)
				return false;
	}
	return true;
}

bool can(int delta)
{
	for (int iRot = 0; iRot < MAXROT; ++iRot) 
		if (isOk(iRot, delta))
			return true;
	return false;
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> nbLig >> nbCol;
	for (int iLig = 0; iLig < nbLig; ++iLig) 
		for (int iCol = 0; iCol < nbCol; ++iCol) 
			cin >> altitude[0][iLig][iCol];
	for (int iLig = 0; iLig < nbLig; ++iLig) 
		for (int iCol = 0; iCol < nbCol; ++iCol) 
		{
			altitude[1][iLig][iCol] = altitude[0][iLig][nbCol - iCol-1];
			altitude[2][iLig][iCol] = altitude[0][nbLig-iLig-1][iCol];
			altitude[3][iLig][iCol] = altitude[0][nbLig-iLig-1][nbCol-iCol-1];
		}
	for (int iLig = 0; iLig < nbLig; ++iLig) 
		for (int iCol = 0; iCol < nbCol; ++iCol) 
			petit = min(petit, altitude[0][iLig][iCol]),
						grand = max(grand, altitude[0][iLig][iCol]);
	int lo(0), up(1e9);
	while (lo < up)
	{
		int mid = (lo + up)/2;
		if (can(mid))
			up = mid;
		else
			lo = mid + 1;
	}
	cout << lo << endl;
}

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