fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int MAXV = 1000000;
  7.  
  8. int n, m;
  9. vector<vector<int>> a;
  10. vector<vector<int>> comp;
  11. vector<vector<ll>> ans;
  12.  
  13. vector<vector<pair<int,int>>> components;
  14. vector<int> freq(MAXV + 1, 0);
  15.  
  16. int dx[4] = {-1,1,0,0};
  17. int dy[4] = {0,0,-1,1};
  18.  
  19. void dfs(int x,int y,int id)
  20. {
  21.     comp[x][y]=id;
  22.     components[id].push_back({x,y});
  23.  
  24.     for(int k=0;k<4;k++)
  25.     {
  26.         int nx=x+dx[k];
  27.         int ny=y+dy[k];
  28.  
  29.         if(nx<0||ny<0||nx>=n||ny>=m) continue;
  30.         if(comp[nx][ny]!=-1) continue;
  31.         if(a[nx][ny]==-1) continue;          // blocked cell
  32.  
  33.         dfs(nx,ny,id);
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.     cin>>n>>m;
  40.  
  41.     a.assign(n, vector<int>(m));
  42.     comp.assign(n, vector<int>(m,-1));
  43.     ans.assign(n, vector<ll>(m,0));
  44. ll block = 0;
  45.     for(int i=0;i<n;i++)
  46.     {
  47.         for(int j=0;j<m;j++)
  48.         {
  49.             cin>>a[i][j];
  50.  
  51.             if(a[i][j]>=0)
  52.                 freq[a[i][j]]++;
  53.             else block++;    
  54.         }
  55.     }
  56.  
  57.     // Find connected components
  58.     int id=0;
  59.     components.resize(n*m);
  60.  
  61.     for(int i=0;i<n;i++)
  62.     {
  63.         for(int j=0;j<m;j++)
  64.         {
  65.             if(a[i][j]>=0 && comp[i][j]==-1)
  66.             {
  67.                 dfs(i,j,id);
  68.                 id++;
  69.             }
  70.         }
  71.     }
  72.  
  73.     components.resize(id);
  74.    ll tot = 0;
  75.     // Process every component
  76.     for(auto &cells: components)
  77.     {
  78.         // Remove current component from frequency table
  79.         for(auto [x,y]:cells)
  80.         {
  81.             freq[a[x][y]]--;
  82.         }
  83.  
  84.         // Compute answers
  85.         for(auto [x,y]:cells)
  86.         {
  87.             int val=a[x][y];
  88.             ll sum=0;
  89.  
  90.             for(int multiple=val;multiple<=MAXV;multiple+=val)
  91.             {
  92.                 sum += 1LL * multiple * freq[multiple];
  93.             }
  94.  
  95.            tot+=sum;
  96.         }
  97.  
  98.         // Restore frequencies
  99.         for(auto [x,y]:cells)
  100.         {
  101.             freq[a[x][y]]++;
  102.         }
  103.     }
  104.  
  105.    cout<<tot-block;
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 6980KB
comments (?)
stdin
copy 
1 1
1
stdout
copy 
Standard output is empty
https://ideone.com/pkfywh
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

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!