提出 #54603261

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>  ordered_set;
// member functions : order_of_key(k){no_of_ele < k} find_by_order(k){kth ele}

const ll M = 998244353;
const ll N = 2e5 + 69;
const ll lmax = 2e18;
const ll lmin = -2e18;
//  ... --- ... 

// --------------------------------------------------------------
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
struct comp {
    bool operator()(const vector<ll> &a, const vector<ll> &b)
    {
        if(a[0] != b[0])
            return a[0] > b[0];
        if(a[1] != b[1])
            return a[1] < b[1];
        return true;
    }
};
// --------------------------------------------------------------

void solve()
{
    ll h, w, k, s_x, s_y; 
    cin >> h >> w >> k >> s_x >> s_y;
    vector<vector<ll>> a(h + 1, vector<ll> (w + 1)), dp(h + 1, vector<ll> (w + 1, -1));
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            cin >> a[i][j];
    priority_queue<vector<ll>, vector<vector<ll>>, comp> pq;
    pq.push({0, 0, s_x, s_y}); // moves, cost
    dp[s_x][s_y] = 0;
    while(!pq.empty())
    {
        auto p = pq.top();
        pq.pop();
        // go in all directions and if not visited visit the cell
        for(int i = 0; i < 4; i++)
        {
            int x = p[2] + dx[i], y = p[3] + dy[i];
            if(x > 0 && y > 0 && x <= h && y <= w && dp[x][y] == -1)
            {
                dp[x][y] = dp[p[2]][p[3]] + a[x][y];
                pq.push({p[0] + 1, dp[x][y], x, y});
            }
        }
    }
    ll ans = a[s_x][s_y] * k;
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            int dist = abs(i - s_x) + abs(j - s_y);
            if(dist <= k)
            {
                ans = max(ans, dp[i][j] + ((k - dist) * a[i][j]));
            }
        }
    }
    cout << ans;
    // 100000000000
    // 100000000200
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    solve();
    return 0;
}

提出情報

ジャッジ結果