Submission #1180195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180195		miniob	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	366 ms	16240 KiB

joioi

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

vector<vector<int>> tab;
int minn, maxx, h, w;

bool spr(int sr)
{
	int pop = w - 1;
	for(int i = 0; i < h; i++)
	{
		int gdzie = -1;
		for(int j = 0; j <= pop; j++)
		{
			if(tab[i][j] - minn > sr)
			{
				//cout << i << " " << j << endl;
				j = w + 7;
			}
			else
			{
				gdzie = j;
			}
		}
		pop = gdzie;
		for(int j = pop + 1; j < w; j++)
		{
			if(maxx - tab[i][j] > sr)
			{
				return false;
			}
		}
	}
	return true;
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	minn = INT_MAX;
	maxx = INT_MIN;
	int odp = INT_MAX;
	cin >> h >> w;
	tab.resize(h);
	for(int i = 0; i < h; i++)
	{
		tab[i].resize(w);
		for(int j = 0; j < w; j++)
		{
			cin >> tab[i][j];
			minn = min(minn, tab[i][j]);
			maxx = max(maxx, tab[i][j]);
		}
	}
	//cout << minn << " " << maxx << endl;
	//cout << spr(10) << endl;
	int l = 0, r = maxx;
	while (l < r) 
	{
        int sr = (l + r) / 2;
        //cout << spr(sr) << " " << sr << endl;
        if (spr(sr)) 
        {
            r = sr;
        }
        else 
        {
            l = sr + 1;
        }
    }
	odp = min(odp, l);
	for(int i = 0; i < h; i++)
	{
		reverse(tab[i].begin(), tab[i].end());
	}
	l = 0, r = maxx;
	while (l < r) 
	{
        int sr = (l + r) / 2;
        if (spr(sr)) 
        {
            r = sr;
        }
        else 
        {
            l = sr + 1;
        }
    }
	odp = min(odp, l);
	for(int i = 0; i < w; i++)
	{
		for(int j = 0; j < h / 2; j++)
		{
			swap(tab[j][i], tab[h - j - 1][i]);
		}
	}
	l = 0, r = maxx;
	while (l < r) 
	{
        int sr = (l + r) / 2;
        if (spr(sr)) 
        {
            r = sr;
        }
        else 
        {
            l = sr + 1;
        }
    }
	odp = min(odp, l);
	for(int i = 0; i < h; i++)
	{
		reverse(tab[i].begin(), tab[i].end());
	}
	l = 0, r = maxx;
	while (l < r) 
	{
        int sr = (l + r) / 2;
        if (spr(sr)) 
        {
            r = sr;
        }
        else 
        {
            l = sr + 1;
        }
    }
	odp = min(odp, l);
	cout << odp << endl;
	return 0;
}

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