Submission #74232042

---

Source Code Expand

#include <bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<long long> vll;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#define endl '\n'
ll mod = 1e9+7 ;
int p1 = 31 , p2 = 91 ;
ll mod1= 1e9+7 , mod2 = 1e9+9 ;


void solve() {
    ll h , w , x ; cin >> h >> w >> x ;
    ll p , q ; cin >> p >> q ;
    ll adj[h][w] ;
    for(int i = 0 ; i < h ; ++i) {
        for(int j = 0 ; j < w  ;++j) {
            cin >>adj[i][j];
        }
    }
    set<pair<ll,pair<ll,ll>>> e ;
    ll ans = adj[p-1][q-1] ;
    int visited[h][w] ;
    memset(visited,0,sizeof(visited)) ;
    visited[p-1][q-1] = 1 ;
    vector<int> v= {-1,0,+1,0} , vv ={0,1,0,-1};
    for(int i = 0 ; i < 4 ; ++i) {
        int x = p-1 + v[i] ;
        int y = q-1 + vv[i] ;
        if(x<h && x>=0 && y<w && y>=0) {
            e.insert({adj[x][y],{x,y}}) ;
        }
    }


    while(! e.empty()) {

        auto it  = e.begin();
        auto i = *it ;
        e.erase(it) ;
        visited[i.second.first][i.second.second] = 1 ;

        if((1.0 *i.first)  >= ((1.0*ans)/x ) ) break ;
        ans+=i.first ;
        for(int ii = 0 ; ii < 4 ; ++ii) {
            int x = i.second.first + v[ii] ;
            int y = i.second.second + vv[ii] ;
            if(x<h && x>=0 && y<w && y>=0 && (!visited[x][y])) {
                e.insert({adj[x][y],{x,y}}) ;
            }
        }

    }
    cout << ans << endl ;
    
}




int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result