Submission #221488

#	Time	Username	Problem	Language	Result	Execution time	Memory
221488		kshitij_sodani	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1587 ms	70648 KiB

joioi

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>

#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>

#include <functional>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <numeric>
#include <random>
#include <ratio>
#include <sstream>
#include <utility>

#include <bitset>
#include <deque>
#include <queue>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <string>
#include <set>

using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
llo n,m;
llo it[2001][2001];
llo mi=1000000001;
llo ma=0;
llo check(){
	llo low=0;
	llo high=ma-1;
	while(low<high){
		llo mid=(low+high)/2;
		llo st=1;
		llo ll=0;
		for(llo i=0;i<n;i++){
			for(llo j=0;j<m;j++){
				if(it[i][j]<ma-mid){
					ll=max(ll,j+1);
				}
			}
			for(llo j=0;j<ll;j++){
				if(it[i][j]>mi+mid){
					st=0;
				}
			}
		}
		if(st){
			high=mid;
		}
		else{
			low=mid+1;
		}
	}
	return low;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m;j++){
			cin>>it[i][j];
			ma=max(ma,it[i][j]);
			mi=min(mi,it[i][j]);
		}
	}
	llo ans=check();
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m/2;j++){
			swap(it[i][j],it[i][m-j-1]);
		}
	}
	ans=min(ans,check());
	for(llo i=0;i<n/2;i++){
		for(llo j=0;j<m;j++){
			swap(it[i][j],it[n-i-1][j]);
		}
	}
	ans=min(ans,check());
	for(llo i=0;i<n;i++){
		for(llo j=0;j<m/2;j++){
			swap(it[i][j],it[i][m-j-1]);
		}
	}
	ans=min(ans,check());
	cout<<ans<<endl;



	return 0;
}

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