Thin Ice

input/code.cpp: In function 'int main()':
input/code.cpp:136:8: warning: unused variable 'stop' [-Wunused-variable]
  136 |     ll stop=1000;
      |        ^~~~

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
 
#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl
 
#define umap unordered_map
#define uset unordered_set
 
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
 
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
 
const ll INF = 1'000'000'007;
 
struct UnionFind {
    vll p,rank;
    ll n;
    UnionFind(ll N) : n(N) {
        p.resize(n);
        rep(i,0,n) p[i]=i;
        rank.assign(n,0);
    }
 
    ll find(ll i) { return p[i]==i?i:p[i]=find(p[i]); }
    bool unite(ll i,ll j) {
        i=find(i);
        j=find(j);
        if(i==j) return 0;
 
        if(rank[i]<rank[j]) swap(i,j);
        p[j]=i;
        if(rank[i]==rank[j]) ++rank[i];
 
        return 1;
    }
};
 
ll rows,cols,n;
vll vals;
vvll graph;
 
vll counts;
 
void dfs(ll u,ll p,ll mind,ll steps) {
    if(!steps) return;
    mind=min(mind,vals[u]);
    ++counts[mind];
    trav(v,graph[u]) if(v!=p) dfs(v,u,mind,steps-1);
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
 
    cin>>rows>>cols;
    n=rows*cols;
    graph.resize(n);
 
    ll maxd=0;
    rep(i,0,rows) rep(j,0,cols) {
        ll d;
        cin>>d;
        vals.pb(d);
        maxd=max(maxd,d);
    }
 
    vector<pair<ll,pll>> edges;
    rep(i,0,rows) rep(j,0,cols) {
        ll u=i*cols+j;
        if(i+1<rows) {
            ll v=(i+1)*cols+j;
            edges.pb({min(vals[u],vals[v]),{u,v}});
        }
 
        if(j+1<cols) {
            ll v=i*cols+j+1;
            edges.pb({min(vals[u],vals[v]),{u,v}});
        }
    }
 
    sort(all(edges),greater<>());
    UnionFind ufds(n);
    trav(edge,edges) {
        ll u,v;
        tie(u,v)=edge.second;
        if(ufds.unite(u,v)) {
            graph[u].pb(v);
            graph[v].pb(u);
            //cout<<vals[u]<<' '<<vals[v]<<endl;
        }
    }
    //cout<<endl;
 
    ll steps=n+1;
    if(n>1000) steps=5;
    ll ans=0;
    vpll roots;
    rep(row,0,rows) {
        rep(j,0,2) {
            ll col=0;
            if(j) col=cols-1;
            ll u=row*cols+col;
            roots.emplace_back(vals[u],u);
        }
    }
 
    rep(col,0,cols) {
        rep(j,0,2) {
            ll row=0;
            if(j) row=rows-1;
            ll u=row*cols+col;
            roots.emplace_back(vals[u],u);   
        }
    }
 
    ll stop=1000;
    rep(i,0,min(sz(roots),sz(roots))) {
        pll item=roots[i];
        counts.assign(maxd+1,0);
        ll u=item.second;
        dfs(u,u,INF,steps);
        ll curans=0;
        rep(i,0,maxd+1) curans+=min(i-curans,counts[i]);
        ans=max(ans,curans);
    }
    cout<<ans<<endl;
    return 0;
}

Test 1

Group: 1, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 5, 6

Verdict: ACCEPTED

Test 6

Group: 1, 5, 6

Verdict: ACCEPTED

Test 7

Group: 1, 5, 6

Verdict: ACCEPTED

Test 8

Group: 1, 5, 6

Verdict: ACCEPTED

Test 9

Group: 1, 2, 5, 6

Verdict: ACCEPTED

Test 10

Group: 2, 6

Verdict: ACCEPTED

Test 11

Group: 2, 6

Verdict: ACCEPTED

Test 12

Group: 2, 6

Verdict: ACCEPTED

Test 13

Group: 2, 6

Verdict: ACCEPTED

Test 14

Group: 2, 6

Verdict: ACCEPTED

Test 15

Group: 2, 6

Verdict: ACCEPTED

Test 16

Group: 2, 6

Verdict: ACCEPTED

Test 17

Group: 2, 6

Verdict: ACCEPTED

Test 18

Group: 2, 6

Verdict: ACCEPTED

Test 19

Group: 2, 6

Verdict: ACCEPTED

Test 20

Group: 2, 6

Verdict: ACCEPTED

Test 21

Group: 2, 6

Verdict: ACCEPTED

Test 22

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 23

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 24

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 25

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 26

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 27

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 28

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 5, 6

Verdict: ACCEPTED

Test 36

Group: 5, 6

Verdict: ACCEPTED

Test 37

Group: 5, 6

Verdict: ACCEPTED

Test 38

Group: 5, 6

Verdict: ACCEPTED

Test 39

Group: 5, 6

Verdict: ACCEPTED

Test 40

Group: 5, 6

Verdict: ACCEPTED

Test 41

Group: 5, 6

Verdict: ACCEPTED

Test 42

Group: 6

Verdict: WRONG ANSWER

Test 43

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 6

Verdict: WRONG ANSWER

Test 45

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 47

Group: 6

Verdict: WRONG ANSWER

Test 48

Group: 6

Verdict: TIME LIMIT EXCEEDED