不光卡 long long 还卡 __int128;
还卡 set:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int n, m, _x, _y, vis[N][N];
int p, a[N][N], ans;
struct node {
int val;
int x, y;
node() {}
node(int Val, int X, int Y) {val = Val, x = X, y = Y;}
friend bool operator < (const node &x, const node &y) {
return x.val < y.val;
}
friend bool operator > (const node &x, const node &y) {
return x.val > y.val;
}
};
priority_queue <node, vector <node>, greater <node>> q;
signed main() {
scanf("%lld%lld%lld%lld%lld", &n, &m, &p, &_x, &_y);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%lld", &a[i][j]);
ans = a[_x][_y];
vis[_x][_y] = 1;
for (int i = 0; i < 4; i++) {
int sx = _x + dx[i], sy = _y + dy[i];
if (sx < 1 || sx > n || sy < 1 || sy > m || vis[sx][sy]) continue;
q.push(node(a[sx][sy], sx, sy));
//if (sx == 2 && sy == 2) cerr << "cao" << endl;
vis[sx][sy] = 1;
}
while (!q.empty()) {
node u = q.top();
int x = u.x, y = u.y;
//cerr << x << " " << y << endl;
//if (x == 2 && y == 2) cerr << "cao!" << endl;
if (__int128(a[x][y]) * __int128(p) >= __int128(ans)) break;
q.pop();
//cerr << "114514 " << q.size() << endl;
ans += a[x][y];
for (int i = 0; i < 4; i++) {
int sx = x + dx[i], sy = y + dy[i];
if (sx < 1 || sx > n || sy < 1 || sy > m || vis[sx][sy]) continue;
//cerr << q.size() << endl;
q.push(node(a[sx][sy], sx, sy));//cerr << "::" << sx << " " << sy << endl;
//cerr << q.size() << endl;
vis[sx][sy] = 1;
}
//cerr << ";;" << q.size() << endl;
}
printf("%lld\n", ans);
return 0;
}
和
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int n, m, _x, _y, vis[N][N];
int p, a[N][N], ans;
struct node {
int val;
int x, y;
node() {}
node(int Val, int X, int Y) {val = Val, x = X, y = Y;}
friend bool operator < (const node &x, const node &y) {
return x.val < y.val;
}
};
set <node> q;
signed main() {
scanf("%lld%lld%lld%lld%lld", &n, &m, &p, &_x, &_y);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%lld", &a[i][j]);
ans = a[_x][_y];
vis[_x][_y] = 1;
for (int i = 0; i < 4; i++) {
int sx = _x + dx[i], sy = _y + dy[i];
if (sx < 1 || sx > n || sy < 1 || sy > m || vis[sx][sy]) continue;
q.insert(node(a[sx][sy], sx, sy));
if (sx == 2 && sy == 2) cerr << "cao" << endl;
vis[sx][sy] = 1;
}
while (!q.empty()) {
node u = *q.begin();
int x = u.x, y = u.y;
cerr << x << " " << y << endl;
if (x == 2 && y == 2) cerr << "cao!" << endl;
if (__int128(a[x][y]) * __int128(p) >= __int128(ans)) break;
q.erase(q.begin());
cerr << "114514 " << q.size() << endl;
ans += a[x][y];
for (int i = 0; i < 4; i++) {
int sx = x + dx[i], sy = y + dy[i];
if (sx < 1 || sx > n || sy < 1 || sy > m || vis[sx][sy]) continue;
cerr << q.size() << endl;
q.insert(node(a[sx][sy], sx, sy));cerr << "::" << sx << " " << sy << endl;
cerr << q.size() << endl;
vis[sx][sy] = 1;
}
cerr << ";;" << q.size() << endl;
}
printf("%lld\n", ans);
return 0;
}
有什么区别!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!??????????????????????????????????????????????????????????????????????????????????????????