fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll MOD = 1e9+7;
  6. const int N = 1005;
  7. const int dirx[]={1,0,-1,0};
  8. const int diry[]={0,1,0,-1};
  9.  
  10. struct node{
  11.     int x,y,v;
  12. }a[N];
  13.  
  14. int mat[N][N],n,m,vis[N][N];
  15. queue<pair<int,pair<int,int> > >q;
  16. bool ok(int x,int y){
  17.     return x>0&&x<=n&&y>0&&y<=m;
  18. }
  19. bool cmp(const node &lhs,const node &rhs){
  20.     return lhs.v>rhs.v;
  21. }
  22. int main()
  23. {
  24.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  25.  
  26.     int k;
  27.     cin>>n>>m>>k;
  28.  
  29.     for(int i=1;i<=k;i++){
  30.         cin>>a[i].x>>a[i].y>>a[i].v;
  31.     }
  32.  
  33.  
  34.     sort(a+1,a+1+n,cmp);
  35.     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mat[i][j]=10000000;
  36.     int x,y,v,posx,posy,d,ans,newx,newy,newd,vrednost;
  37.     int prev=-1;
  38.  
  39.     for(int i=1;i<=k;i++){
  40.         q.push({a[i].x,{a[i].y,0}});
  41.         vis[a[i].x][a[i].y]=i;
  42.         while(!q.empty()){
  43.             auto p=q.front();
  44.             q.pop();
  45.             mat[p.first][p.second.first]=(p.second.second+a[i].v-1)/a[i].v;
  46.             for(int j=0;j<4;j++){
  47.                 newx=p.first+dirx[j];
  48.                 newy=p.second.first+diry[j];
  49.                 vrednost=(p.second.second+a[i].v)/a[i].v;
  50.                 if(ok(newx,newy)&&vis[newx][newy]!=i&&vrednost<=mat[newx][newy]){
  51.                     q.push({newx,{newy,p.second.second+1}});
  52.                     vis[newx][newy]=i;
  53.                 }
  54.             }
  55.         }
  56.     }
  57.     int ans2=-1;
  58.     int p,t;
  59.     for(int i=1;i<=n;i++){
  60.         for(int j=1;j<=m;j++){
  61.             if(mat[i][j]>ans2){
  62.                 ans2=mat[i][j];
  63.                 p=i;
  64.                 t=j;
  65.             }
  66.         }
  67.     }
  68.     cout<<p<<" "<<t;
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
480968328 21999
https://ideone.com/vp6rZy
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!