Submission #1239420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239420		PlayVoltz	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	320 KiB

joioi

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m, mx=0, mn=LLONG_MAX/2;
vector<vector<int> > vect;

bool check(int mid){
	vector<vector<int> > temp=vect;
	for (int ooga=0; ooga<4; ++ooga){
		bool can=1;
		swap(n, m);
		vector<vector<int> > graph(n, vector<int>(m));
		for (int i=0; i<n; ++i)for (int j=0; j<m; ++j)graph[i][j]=temp[j][n-i-1];
		temp=graph;
		vector<int> p(n);
		for (int i=0, j, end=m; i<n; ++i){
			j=0;
			for (;j<end;++j)if (graph[i][j]>mn+mid)break;
			p[i]=end=j;
		}
		for (int i=0; i<n; ++i)for (int j=p[i]; j<m; ++j)if (graph[i][j]<mx-mid)can=0;
		if (can)return 1;
	}
	return 0;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	vect.resize(n, vector<int>(m));
	for (int i=0; i<n; ++i)for (int j=0; j<m; ++j)cin>>vect[i][j], mn=min(mn, vect[i][j]), mx=max(mx, vect[i][j]);
	int low=-1, high=LLONG_MAX/2;
	while (low+1<high){
		int mid=(low+high)/2;
		if (check(mid))high=mid;
		else low=mid;
	}
	cout<<high;
}

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