SB ABC 出题人
  • 板块学术版
  • 楼主I_Love_DS
  • 当前回复23
  • 已保存回复23
  • 发布时间2024/12/14 21:46
  • 上次更新2024/12/15 11:00:04
查看原帖
SB ABC 出题人
1118614
I_Love_DS楼主2024/12/14 21:46

不光卡 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;
}

有什么区别!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!??????????????????????????????????????????????????????????????????????????????????????????

2024/12/14 21:46
加载中...