Submission #496945

#TimeUsernameProblemLanguageResultExecution timeMemory
496945armashkaMaxcomp (info1cup18_maxcomp)C++17
15 / 100
143 ms23860 KiB
#include <bits/stdc++.h> //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define all(v) v.begin(),v.end() #define pb push_back #define sz size() #define ft first #define sd second using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef unsigned long long ull; const int N = 1e6 + 5; const ll M = 1e8; const ll inf = 1e18; const ll mod = 1e9; const double Pi = acos(-1); ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;} ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;} ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); } bool odd(ll n) { return (n % 2 == 1); } bool even(ll n) { return (n % 2 == 0); } ll n, m, a[N], ans= -inf; vector <ll> g[N]; void bfs(ll s) { queue <ll> q; vector <ll> d(n * m + 5, inf), mn(n * m + 5, inf), mx(n * m + 5, 0), p(n * m + 5, -inf); q.push(s); d[s] = 1; mn[s] = mx[s] = a[s]; while (q.sz) { ll v = q.front(); q.pop(); for (auto to : g[v]) { ll cur = max(mx[v], a[to]) - min(mn[v], a[to]) - (d[v] + 1); if (p[to] < cur) { p[to] = cur; mx[to] = max(mx[v], a[to]); mn[to] = min(mn[v], a[to]); d[to] = d[v] + 1; q.push(to); } } } ll res = 0, f = -1; for (int i = 1; i <= n * m; ++ i) res = max(res, p[i]); ans = max(ans, res); } const void solve(/*Armashka*/) { cin >> n >> m; for (int i = 1; i <= n * m; ++ i) cin >> a[i]; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { int cur = (i - 1) * m + j; int to = (i - 1) * m + j + 1; if (j < m) { g[cur].pb(to); g[to].pb(cur); } to = (i * m) + j; if (i < n) { g[cur].pb(to); g[to].pb(cur); } } } for (int i = 1; i <= n * m; ++ i) bfs(i); cout << ans << "\n"; } signed main() { fast; //freopen("divide.in", "r", stdin); //freopen("divide.out", "w", stdout); int tt = 1; //cin >> tt; while (tt --) { solve(); } } /* 5 4 4 1 2 3 1 3 4 5 3 4 5 2 3 2 1 3 1 1 3 5 2 3 4 5 2 1 3 1 */

Compilation message (stderr)

maxcomp.cpp: In function 'void bfs(ll)':
maxcomp.cpp:54:14: warning: unused variable 'f' [-Wunused-variable]
   54 |  ll res = 0, f = -1;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...