#include using namespace std; using ll=long long; ll linf=1000000000000000000; template bool chmax(T& a,T b){ if(a bool chmin(T& a,T b){ if(a>b){ a=b; return true; }else return false; } vector dx={1,0,-1,0}; vector dy={0,1,0,-1}; struct bomb{ ll c,l; int id; vector> range; bomb(){} bomb(ll c,ll l,int id):c(c),l(l),id(id){range.resize(l);} }; struct bomb_instance{ int x,y; int id; set blown_shops; bomb_instance(){} bomb_instance(int x,int y,int id):x(x),y(y),id(id){} }; bool operator==(bomb_instance& a,bomb_instance &b){ return a.x==b.x&&a.y==b.y&&a.id==b.id; } int n,m; vector bombs; vector locates; vector grid; string ans; int ans_count; map,int> shop_num; vector> shop_location; set> shops; vector blown_num; void read_input(){ cin>>n>>m; ans_count=0; bombs.resize(m); grid.resize(n); for(int i=0;i>grid[i]; for(int i=0;i>c>>l; bombs[i]=bomb(c,l,i); for(int j=0;j>a>>b; bombs[i].range[j]=make_pair(a,b); } } sort(bombs.begin(),bombs.end(),[](bomb a,bomb b)->bool{ return a.c copy_grid=grid; auto good_bomb=[&](int x,int y)->void{ bomb_instance res; int max_score=0; for(int i=0;i0||ly>0)continue; }else{ if(lx>0||ly<0)continue; } }else{ if(y0)continue; }else{ if(lx<0||ly<0)continue; } } if(abs(nx)+abs(ny)=n||my<0||my>=n)continue; if(copy_grid[mx][my]!='.')score++; } if(score>max_score){ max_score=score; res=bomb_instance(x-nx,y-ny,bombs[i].id); } } int index=0; for(int i=0;i=n||res.y+ly<0||res.y+ly>=n)continue; copy_grid[res.x+lx][res.y+ly]='.'; if(shop_num.count({res.x+lx,res.y+ly})){ res.blown_shops.insert(shop_num[{res.x+lx,res.y+ly}]); } } for(int x:res.blown_shops)blown_num[x]++; locates.push_back(res); }; for(int i=0;i=n/2||i-j>=n/2)continue; int x=j,y=i-j; if(copy_grid[x][y]!='.')good_bomb(x,y); if(copy_grid[n-1-x][y]!='.')good_bomb(n-1-x,y); if(copy_grid[x][n-1-y]!='.')good_bomb(x,n-1-y); if(copy_grid[n-1-x][n-1-y]!='.')good_bomb(n-1-x,n-1-y); //for(string s:copy_grid)cout<next_x){ for(int i=0;inext_y){ for(int i=0;inow_y){ for(int i=0;i last_bomb; for(bomb_instance b:locates){ if(b.blown_shops.count(min_index))last_bomb.push_back(b); } for(bomb_instance b:last_bomb){ for(int i=0;i