Submission #60737151

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
vector<pair<int, int>> prop(int x, int y, int h, int w) {
    vector<pair<int, int>> ans;
    if (x > 0) ans.push_back({x-1, y});
    if (y > 0) ans.push_back({x, y-1});
    if (x < h-1) ans.push_back({x+1, y});
    if (y < w-1) ans.push_back({x, y+1});
    return ans;
}
signed main() {
    int h, w, x; cin >> h >> w >> x;
    ll x1 = x;
    int p, q; cin >> p >> q;
    int grid[h][w]; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> grid[i][j];
    ll power = grid[p-1][q-1];
    int visited[h][w];
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) visited[i][j] = -1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
vector<pair<int, int>> prop(int x, int y, int h, int w) {
    vector<pair<int, int>> ans;
    if (x > 0) ans.push_back({x-1, y});
    if (y > 0) ans.push_back({x, y-1});
    if (x < h-1) ans.push_back({x+1, y});
    if (y < w-1) ans.push_back({x, y+1});
    return ans;
}

signed main() {
    int h, w, x; cin >> h >> w >> x;
    ll x1 = x;
    int p, q; cin >> p >> q;
    int grid[h][w]; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> grid[i][j];
    ll power = grid[p-1][q-1];
    int visited[h][w];
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) visited[i][j] = -1;
    visited[p-1][q-1] = 0;
    priority_queue <pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq;
    for (auto i:prop(p-1, q-1, h, w)) {
        pq.push({grid[i.first][i.second], {i.first, i.second}});
        visited[i.first][i.second] = 1;
    }
    while (pq.size() > 0 and pq.top().first*x1 < power) {
        auto cur = pq.top();
        pq.pop();
        power += cur.first;
        //now propogate
        for (auto i:prop(cur.second.first, cur.second.second, h, w)) {
            if (visited[i.first][i.second] == -1) {
                visited[i.first][i.second] = 1;
                pq.push({grid[i.first][i.second], {i.first, i.second}});
            }
        }
    }
    cout << (int)power;
}

Submission Info

Judge Result