求昨晚E优化/卡常
  • 板块学术版
  • 楼主wuenzi
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/15 11:25
  • 上次更新2024/12/15 15:17:45
查看原帖
求昨晚E优化/卡常
1110691
wuenzi楼主2024/12/15 11:25

rt

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define mp make_pair
#define x first 
#define y second 
#pragma GCC optsize(2)
using namespace std;
int n,m,X,x11,y11; 
int a[505][505];
int v[505][505];
/*
0:未访问
1:已访问
-1:待处理 
*/
int ans=0;
queue<pair<int,int> > q;
vector<pair<int,int> >dcl;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
	cin>>n>>m>>X>>x11>>y11;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	q.push(mp(x11,y11));
	v[x11][y11]=1;
	while(!q.empty()){
		auto l=q.front();q.pop();
		ans+=a[l.x][l.y];
		for(auto i=dcl.begin();i!=dcl.end();i++){
			if(v[i->x][i->y]==-1&&a[i->x][i->y]<ans*1.0/X){
				q.push(mp(i->x,i->y));
				v[i->x][i->y]=1;
				auto j=i;j--;
				dcl.erase(i);
				i=j;
			}
		}
		for(int i=0;i<4;i++){
			int nx=l.x+dx[i],ny=l.y+dy[i];
			if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&v[nx][ny]==0){
				if(a[nx][ny]<ans*1.0/X){
					q.push(mp(nx,ny));
					v[nx][ny]=1;
				}else{
					dcl.push_back(mp(nx,ny));
					v[nx][ny]=-1;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}
2024/12/15 11:25
加载中...