Why E WA*4?
  • 板块学术版
  • 楼主wo_hen_la
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/12/14 22:14
  • 上次更新2024/12/15 09:33:39
查看原帖
Why E WA*4?
794701
wo_hen_la楼主2024/12/14 22:14
#include <bits/stdc++.h>
using namespace std;

#define sp putchar(' ')
#define en putchar('\n')
#define pb push_back
#define int __int128
#define HP 1000000000000002097
#define umap unordered_map
#define mk make_pair
int read(){ char ch=getchar();int x=0,f=1;while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f; }
void print(int x){ if(x<0) putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0'); }

const int N=505,P=998244353;

int n,m;
double xx;
int a[N][N];
bool vis[N][N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > r;
int zh(int x,int y)
{
	return (x-1)*m+y;
}
void mdf(int &x,int &y,int d)
{
	x=d/m+!(d%m==0);
	y=d-(x-1)*m;
}
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	n=read();m=read();xx=read();
	int p,q;
	p=read();q=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=read();
		}
	}
	int now=a[p][q];
	vis[p][q]=1;
	vis[p+1][q]=1;
	vis[p][q+1]=1;
	vis[p-1][q]=1;
	vis[p][q-1]=1;
	r.push(mk(a[p+1][q],zh(p+1,q)));
	r.push(mk(a[p-1][q],zh(p-1,q)));
	r.push(mk(a[p][q+1],zh(p,q+1)));
	r.push(mk(a[p][q-1],zh(p,q-1)));
	/*
	3 3 2
	2 2
	14 6 9
	4 9 20
	17 15 7
	*/
	while(!r.empty()){
		int u=r.top().second,x,y;
		r.pop();
		mdf(x,y,u);
		//cout<<x<<" "<<y<<"\n";
		if(x<1 || y<1 || x>n || y>m) continue;
		if(a[x][y]*xx<now){
		//	cout<<x<<" "<<y<<" ";
			now+=a[x][y];
			for(int i=0;i<4;i++){
				int tx=x+dx[i],ty=y+dy[i];
				if(tx<1 || ty<1 || tx>n || ty>m || vis[tx][ty]) continue;
				r.push(mk(a[tx][ty],zh(tx,ty)));
				vis[tx][ty]=1;
			}
			//cout<<now<<"\n";
		}
		else break;
	}
	print(now);
	return 0;
}






2024/12/14 22:14
加载中...