Submission #1109911

#TimeUsernameProblemLanguageResultExecution timeMemory
1109911ljtunasThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
12 ms4176 KiB
// author : anhtun_hi , nqg #include <bits/stdc++.h> #define ll long long #define ii pair<ll, ll> #define fi first #define se second #define all(x) x.begin(), x.end() #define reset(h, v) memset(h, v, sizeof h) #define Forv(i, a) for(auto& i : a) #define For(i, a, b) for(int i = a; i <= b; ++i) #define Ford(i, a, b) for(int i = a; i >= b; --i) #define c_bit(i) __builtin_popcountll(i) #define Bit(mask, i) ((mask >> i) & 1LL) #define onbit(mask, i) ((mask) bitor (1LL << i)) #define offbit(mask, i) ((mask) &~ (1LL << i)) using namespace std; namespace std { template <typename T, int D> struct _vector : public vector <_vector <T, D - 1>> { static_assert(D >= 1, "Dimension must be positive!"); template <typename... Args> _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {} }; template <typename T> struct _vector <T, 1> : public vector <T> { _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {} }; template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;} template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;} } const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5; const int MAXN = 2e3 + 5; const ll mod = 1e9 + 7; const ll oo = 1e18; //#define int long long int n, m; vector<vector<int>> a; bool vs[MAXN][MAXN]; bool check(int val){ int mn = inf, mx = 0; bool ok = false; mn = inf, mx = 0; reset(vs, 0); For(hang, 0, n - 1){ for(int i = 0, j = -1; i < m; ++i){ while(j < m - 1 && max(a[hang][j + 1], mx) - min(a[hang][j + 1], mn) <= val) { ++j; maximize(mx, a[hang][j]); minimize(mn, a[hang][j]); vs[hang][j] = 1; } } } mn = inf, mx = 0; For(i, 0, n - 1) For(j, 0, m - 1) if(!vs[i][j]) minimize(mn, a[i][j]), maximize(mx, a[i][j]); ok |= (mx - mn <= val); mn = inf, mx = 0; reset(vs, 0); For(hang, 0, n - 1) reverse(all(a[hang])); For(hang, 0, n - 1){ for(int i = 0, j = -1; i < m; ++i){ while(j < m - 1 && max(a[hang][j + 1], mx) - min(a[hang][j + 1], mn) <= val) { ++j; maximize(mx, a[hang][j]); minimize(mn, a[hang][j]); vs[hang][j] = 1; } } } For(hang, 0, n - 1) reverse(all(a[hang])); mn = inf, mx = 0; For(i, 0, n - 1) For(j, 0, m - 1) if(!vs[i][j]) minimize(mn, a[i][j]), maximize(mx, a[i][j]); ok |= (mx - mn <= val); // mn = inf, mx = 0; reset(vs, 0); For(cot, 0, m - 1){ for(int i = 0, j = -1; i < n; ++i){ while(j < n - 1 && max(a[j + 1][cot], mx) - min(a[j + 1][cot], mn) <= val) { ++j; maximize(mx, a[j][cot]); minimize(mn, a[j][cot]); vs[j][cot] = 1; } } } mn = inf, mx = 0; For(i, 0, n - 1) For(j, 0, m - 1) if(!vs[i][j]) minimize(mn, a[i][j]), maximize(mx, a[i][j]); ok |= (mx - mn <= val); // mn = inf, mx = 0; reset(vs, 0); For(cot, 0, m - 1){ for(int i = n - 1, j = n; i >= 0; --i){ while(j > 0 && max(a[j - 1][cot], mx) - min(a[j - 1][cot], mn) <= val) { --j; maximize(mx, a[j][cot]); minimize(mn, a[j][cot]); vs[j][cot] = 1; } } } mn = inf, mx = 0; For(i, 0, n - 1) For(j, 0, m - 1) if(!vs[i][j]) minimize(mn, a[i][j]), maximize(mx, a[i][j]); ok |= (mx - mn <= val); return ok; } void Solve() { cin >> n >> m; a.assign(n, vector<int>(m, 0)); For(i, 0, n - 1) For(j, 0, m - 1) cin >> a[i][j]; int l = -1, r = inf; while(r - l > 1){ int mid = l + r >> 1; if(check(mid)) r = mid; else l = mid; } cout << r << '\n'; // cout << } int32_t main() { cin.tie(0) -> sync_with_stdio(0); if(fopen("JOI17_joioi.inp", "r")) { freopen("JOI17_joioi.inp", "r", stdin); freopen("JOI17_joioi.out", "w", stdout); } int t = 1; // cin >> t; for (int test = 1; test <= t; test++) { Solve(); } return 0; }

Compilation message (stderr)

joioi.cpp: In function 'void Solve()':
joioi.cpp:116:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         int mid = l + r >> 1;
      |                   ~~^~~
joioi.cpp: In function 'int32_t main()':
joioi.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("JOI17_joioi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen("JOI17_joioi.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...