fork download 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. long long int arr[1011][1011],maxi,n,m;
  6. int visited[1011][1011];
  7. int counter=0;
  8. void DFS(int x,int y)
  9. {
  10.     if(visited[x][y] or arr[x][y]==0)return;
  11.     counter++;
  12.     visited[x][y]=1;
  13.     if(x+1<=n && arr[x+1][y]<=arr[x][y])DFS(x+1,y);
  14.     if(x-1>=1 && arr[x-1][y]<=arr[x][y])DFS(x-1,y);
  15.     if(y+1<=m && arr[x][y+1]<=arr[x][y])DFS(x,y+1);
  16.     if(y-1>=1 && arr[x][y-1]<=arr[x][y])DFS(x,y-1);
  17. }
  18.  
  19. int main() {
  20. 	// your code goes here
  21. 	// #ifdef JUDGE
  22.     //freopen("input.txt", "rt", stdin);
  23.     //freopen("output.txt", "wt", stdout);
  24.     // #endif
  25. 	ios_base::sync_with_stdio(0);
  26. 	cin.tie(NULL);
  27. 	cout.tie(NULL);
  28. 	int t;
  29. 	t=1;
  30. 	while(t--)
  31. 	{
  32. 	    int ans=0;
  33. 	    counter=0;
  34. 	    n=500;m=500;
  35. 	    srand(time(NULL));
  36. 	    int i,j;
  37. 	    maxi=0;
  38. 	    for(i=1;i<=n;i++)for(j=1;j<=m;j++){arr[i][j]=(rand())%1000000;maxi=max(arr[i][j],maxi);visited[i][j]=0;}
  39. 	    for(i=1;i<=n;i++)
  40. 	    {
  41. 	        for(j=1;j<=m;j++)
  42. 	        {
  43. 	            if(arr[i][j]==maxi && visited[i][j]==0)
  44. 	            {
  45. 	                ans++;
  46. 	                DFS(i,j);
  47. 	            }
  48. 	        }
  49. 	    }
  50. 	    while(counter!=n*m)
  51. 	    {
  52. 	        maxi=0;
  53. 	        for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(visited[i][j]==0)maxi=max(maxi,arr[i][j]);
  54. 	        for(i=1;i<=n;i++)
  55. 	        {
  56. 	            for(j=1;j<=m;j++)
  57. 	            {
  58. 	                if(arr[i][j]==maxi && visited[i][j]==0)
  59. 	                {
  60. 	                    ans++;
  61. 	                    DFS(i,j);
  62. 	                }
  63. 	            }
  64. 	        }
  65.  
  66. 	    }
  67.  
  68. 	    cout<<ans<<endl;
  69.  
  70. 	}
  71.  
  72. 	return 0;
  73. }
Time limit exceeded #stdin #stdout 5s 28032KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mYM9sw
language:
C++ (gcc 8.3)
created:
7 years 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!