Submission #1174416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174416		hengliao	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	196 ms	48584 KiB

maxcomp

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

const ll inf=1e18;

ll n, m;

ll dx[4]={1, -1, 0, 0};
ll dy[4]={0, 0, 1, -1};

bool inside(ll x, ll y){
    return x>=0 && x<n && y>=0 && y<m;
}

void solve(){
    
    cin>>n>>m;
    vector<vll> a(n, vll(m));
    vector<vll> dis(n, vll(m, inf));
    vector<pair<ll, pll>> v;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            cin>>a[i][j];
            v.pb({a[i][j], {i, j}});
        }
    }
    sort(v.begin(), v.end());
    ll pt=0;
    queue<pair<ll, pll>> q;
    q.push(v[0]);
    dis[v[0].S.F][v[0].S.S]=v[0].F;
    pt++;
    while(!q.empty()){
        while(pt<(ll) v.size() && v[pt].F<=q.front().F){
            if(dis[v[pt].S.F][v[pt].S.S]==inf){
                dis[v[pt].S.F][v[pt].S.S]=v[pt].F;
                q.push(v[pt]);
            }
            pt++;
        }
        auto [d, it]=q.front(); q.pop();
        ll x=it.F;
        ll y=it.S;
        for(ll i=0;i<4;i++){
            ll xx=x+dx[i];
            ll yy=y+dy[i];
            if(inside(xx, yy) && dis[xx][yy]==inf){
                dis[xx][yy]=d+1;
                q.push({dis[xx][yy], {xx, yy}});
            }
        }
    }    
    ll ans=-inf;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            ans=max(ans, a[i][j]-dis[i][j]-1);
        }
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40