Submission #480729

#TimeUsernameProblemLanguageResultExecution timeMemory
480729MonkeyKingThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
2403 ms47572 KiB
#include <numeric> #include <iostream> #include <algorithm> #include <cmath> #include <stdio.h> #include <stdlib.h> #include <vector> #include <map> #include <queue> #include <set> #include <string> #include <string.h> #include <stack> #include <assert.h> #include <bitset> #include <time.h> #define Endl endl #define mp make_pair #define mt make_tuple #define ll long long #define ull unsigned long long #define pii pair<int,int> #define over(A) {cout<<A<<endl;exit(0);} #define all(A) A.begin(),A.end() #define quickcin ios_base::sync_with_stdio(false); const int mod=1000000007; const int gmod=3; const int inf=1039074182; const double eps=1e-9; const double pi=3.141592653589793238462643383279; const ll llinf=2LL*inf*inf; template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;} template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;} inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);} template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;} template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;} template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;} template <typename T> inline T mabs(T x) {return (x<0?-x:x);} using namespace std; int n,m; int a[2005][2005]; int b[2005][2005]; int bel[2005][2005]; pair<int,pii> mn,mx; int res; inline bool check(int mid) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { bel[i][j]=0; if(a[i][j]-mn.first<=mid) bel[i][j]|=1; if(mx.first-a[i][j]<=mid) bel[i][j]|=2; if(!bel[i][j]) return 0; } } int pre=m; for(int i=0;i<n;i++) { for(int j=0;j<pre;j++) { if(bel[i][j]==2) { pre=j; break; } } for(int j=pre;j<m;j++) { if(bel[i][j]==1) return false; } } return true; } void solve() { if(mn.first>=mx.first && mn.second>=mx.second) return; int l=0,r=res-1,mid; while(l<=r) { mid=l+r>>1; if(check(mid)) { res=mid; r=mid-1; } else { l=mid+1; } } } int main() { // freopen("input.txt","r",stdin); cin>>n>>m; mn.first=inf; mx.first=-inf; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",a[i]+j); chmax(mx,mp(a[i][j],mp(i,j))); chmin(mn,mp(a[i][j],mp(i,j))); } } res=mx.first-mn.first; for(int _=0;_<4;_++) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { b[j][n-1-i]=a[i][j]; } } memcpy(a,b,sizeof(b)); swap(mx.second.first,mx.second.second); mx.second.second=n-1-mx.second.second; swap(mn.second.first,mn.second.second); mn.second.second=n-1-mn.second.second; swap(n,m); solve(); } cout<<res<<endl; return 0; }

Compilation message (stderr)

joioi.cpp: In function 'void solve()':
joioi.cpp:84:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   mid=l+r>>1;
      |       ~^~
joioi.cpp: In function 'int main()':
joioi.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d",a[i]+j);
      |    ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...