Submission #1114022

#TimeUsernameProblemLanguageResultExecution timeMemory
1114022Dan4LifeThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
289 ms50512 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) const int N = (int)2e3+10; int n, m, lst[N]; int dp[N][N], pref[N][N]; int a[N][N], b[N][N], c[N][N]; void Rotate(){ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) c[i][j] = b[i][j]; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) b[j][i] = c[i][m-j-1]; swap(n,m); } bool calc(){ for(int k : {0,1}){ memset(dp,0,sizeof(dp)); memset(pref,0,sizeof(pref)); memset(lst,0,sizeof(lst)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ pref[i][j+1] = pref[i][j]+(!b[i][j] or b[i][j]==k); if(b[i][j]==k) lst[i]=j; } } for(int i = 0; i < n; i++){ for(int j = lst[i]; j <= m; j++){ if(pref[i][j]!=j) break; if(!i) dp[i][j]=(j!=m); else{ for(int k = lst[i-1]; k <= j; k++) dp[i][j]|=dp[i-1][k]; } } } bool ok = 0; for(int i = 1; i <= m; i++) ok|=dp[n-1][i]; if(ok) return 1; /* memset(dp,0,sizeof(dp)); for(int i = n-1; i >= 0; i--){ for(int j = lst[i]; j <= m; j++){ if(pref[i][j]!=j) break; if(i==n-1) dp[i][j]=(j!=m); else{ for(int k = lst[i+1]; k <= j; k++) dp[i][j]|=dp[i+1][k]; } } } for(int i = 1; i <= m; i++) ok|=dp[0][i]; if(ok) return 1;*/ } return 0; } bool chk(int R){ memset(b,0,sizeof(b)); int mn = (int)1e9, mx = 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) mn = min(mn, a[i][j]), mx = max(mx, a[i][j]); if(mn+R+1 <= mx-R-1) return 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) b[i][j]=(a[i][j]>mn+R?2:a[i][j]<mx-R); bool ok = 0; for(int i = 0; i < 4; i++) ok|=calc(), Rotate(); return ok; } int main(){ cin >> n >> m; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j]; int l = 0, r = (int)1e9; while(l<r){ int mid = (l+r)/2; if(chk(mid)) r=mid; else l=mid+1; } cout << l << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...