Submission #905002

#TimeUsernameProblemLanguageResultExecution timeMemory
905002Maite_MoraleThe Kingdom of JOIOI (JOI17_joioi)C++14
0 / 100
2 ms8660 KiB
#include<bits/stdc++.h> #define F first #define S second #define MAX 3005 #define oo 1e18 #define mod 1000000007 #define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0); using namespace std; typedef long long ll; #define pll pair<ll , ll> #define vll vector<ll> #define vvll vector<vll> #define vpll vector<pll> ll tmn[5][MAX][MAX],tmx[5][MAX][MAX],n,a[MAX][MAX],m; map<ll,ll> mp; vll v; ll OK(ll x,ll z){ //cout<<x<<": "; ll r=oo,mx=0,c=0; for(int i=1;i<=n;i++){ while(c+1<=m && tmn[1][i][c+1]<x)c++; mx=max(mx,tmx[0][i][c]); }r=min(r,mx); //cout<<mx<<" "; mx=0;c=0; for(int i=n;i>0;i--){ while(c+1<=m && tmn[1][i][c+1]<x)c++; mx=max(mx,tmx[0][i][c]); }r=min(r,mx); //cout<<mx<<" "; mx=0;c=m+1; for(int i=1;i<=n;i++){ while(c-1>=0 && tmn[0][i][c-1]<x)c--; mx=max(mx,tmx[1][i][c]); }r=min(r,mx); //cout<<mx<<" "; mx=0;c=m+1; for(int i=n;i>0;i--){ while(c-1>=m && tmn[0][i][c-1]<x)c--; mx=max(mx,tmx[1][i][c]); }r=min(r,mx); //cout<<mx<<"\n"; if(z==1)return max(abs(r-v[0]),abs(v.back()-x)); if(abs(r-v[0])>=abs(v.back()-x))return 0; return 1; } int main(){ fast_in cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; if(mp[a[i][j]]==0){ mp[a[i][j]]=1; v.push_back(a[i][j]); } } tmx[0][i][0]=tmx[1][i][m+1]=0; tmn[0][i][0]=tmn[1][i][m+1]=oo; for(int j=1;j<=m;j++){ tmx[0][i][j]=max(tmx[0][i][j-1],a[i][j]); tmn[0][i][j]=min(tmn[0][i][j-1],a[i][j]); } for(int j=m;j>0;j--){ tmx[1][i][j]=max(tmx[1][i][j+1],a[i][j]); tmn[1][i][j]=min(tmn[1][i][j+1],a[i][j]); //cout<<tmn[1][i][j]<<" "; }//cout<<"\n"; }sort(v.begin(),v.end()); if(v.size()==1){cout<<0;return 0;} ll p=1,f=v.size();//cout<<f<<" "; while(abs(p-f)!=1){ ll md=(p+f)/2;//cout<<md<<":"; if(OK(v[md],0)==1)p=md; else f=md; } cout<<min(OK(v[p],1),OK(v[f],1)); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...