fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <string>
  6. #include <iomanip>
  7. #include <cmath>
  8. #include <ctime>
  9. #include <numeric>
  10. #include <bitset>
  11. #define endl '\n'
  12. #define ll long long
  13. #define all(n) n.begin() , n.end( )
  14. #define vi vector<int>
  15. #define vvi vector<vi>
  16. #define int long long
  17. #define pii pair<int,int>
  18. #define vpii vector<pair<int,int>>
  19. #define mii map<int,int>
  20. #define si set<int>
  21. #define input(v,n) for(int i = 0 ; i< n ; i++) cin >> v[i]
  22. #define output(v)  for(auto it : v) cout << it << endl;
  23. #define IS_POWER_OF_TWO(n) ((n) && !((n) & ((n) - 1)))
  24. #define bug(...) _f (#__VA_ARGS__,__VA_ARGS__)
  25. #define lb(x,w,z) for(int x=w;x<z;x++)
  26. #define FOR (x,y) for(auto x:y)
  27. #define revlop(a,b,c) for(int a=b;a>=c;a--)
  28.  
  29. // #include <ext/pb_ds/assoc_container.hpp>
  30. // #include <ext/pb_ds/tree_policy.hpp>
  31. // using namespace std;
  32. // using namespace __gnu_pbds;
  33. // template<class t> using ordered_multiset = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
  34. //---------------------------------------------------------------
  35.  
  36. int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
  37. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  38.  
  39. using namespace std;
  40. void fast() {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.     cout.tie(NULL);
  44. }
  45.  
  46. // const ll  N= 2e6+5;
  47. // ll  pre[N],pre2[N],next_arr[N],arr[N],bb[N] ;
  48. /*
  49.  
  50. ll sqrtt(ll n){
  51. ll l{},r= 1000000000+1,mid;
  52. while(r-l>1){
  53.     mid = l+(r-l)/2;
  54.     if( mid * mid > n )r=mid;
  55.     else l =mid;
  56. }
  57. return l;
  58. }
  59.  
  60. ll lcm ( ll a , ll b)
  61. {
  62.     return (a*b)/gcd(a,b);
  63. }
  64.  
  65. ll fast_power(ll a,ll b , int mod){
  66.     ll ans=1;
  67.     while(b){
  68.     if(b&1){
  69.         ans*=a;
  70.         ans%=mod;
  71.     }
  72.     a*=a;
  73.     a%=mod;
  74.     b = (b>>1);
  75. }
  76. return ans;
  77. }
  78. /*
  79. ll gcd ( ll a, ll b)
  80. {
  81.     if ( b == 0 )
  82.         return a;
  83.     return gcd(b, a%b);
  84. }
  85. vector<int> vis(N);
  86. vector<int> prime(N ) ;
  87. void get_prime(){
  88.     prime[0] = 0 , prime[1] = 1 ;
  89.     for (int i = 2 ; i<= N ; i++){
  90.         if ( !prime[i]  ){
  91.             for (int j = i ; j <= N ; j+=i)
  92.                 prime[j] = i ;
  93.  
  94.         }
  95.     }
  96. }
  97.  
  98. vi prims(N);
  99. void seive(int n ){
  100.     prims[0] = prims[1] = 1;
  101.     for (int  i = 2 ; i* i <= n ; i++){
  102.         if ( !prims[i] ){
  103.             prims[i]  = 0 ;
  104.             for (int j = 2*i ; j <= n ; j+=i ){
  105.                 prims[j] = 1;
  106.             }
  107.         }
  108.     }
  109. }
  110.  
  111. vector<int> prim_fac(ll n ){
  112.     vector<int> v;
  113.     for (int i = 2 ; i*i <= n ;i ++ ){
  114.         while (n != 1 ){
  115.             if ( n % i == 0 ){
  116.                 n/=i;
  117.                 v.push_back(i);
  118.             }
  119.             else break;
  120.         }
  121.     }
  122.     return v;
  123. }
  124.  
  125. bool is_prime(int n)
  126. {
  127.     bool isprime = true;
  128.     if ( n == 1)
  129.         return false;
  130.     for (int i = 2 ; i * i <= n ; i++)
  131.     {
  132.         if ( n %i == 0 )
  133.             isprime = false;
  134.     }
  135.     return isprime;
  136. }*/
  137.  
  138.  
  139.  
  140. const  ll oo = 1e18+2 , mod = 1e9+7 ;
  141. const  int N = 2e4+5 , M = 1e6+5;
  142.  
  143.  
  144.  
  145. int ans = 0 ;
  146. map<int , map<int,int>> mp;
  147. map<int,int> calc;
  148.  
  149. bool flag = false;
  150.  
  151. int s, n, m ;
  152.  
  153. int dxx[] = {0, 0, 1, -1};
  154. int dyy[] = {1, -1, 0, 0};
  155.  
  156. bool valid ( int i , int j ){
  157.     return i>= 0 && i<n && j >= 0 && j<m;
  158. }
  159.  
  160. int cont = 0;
  161.  
  162. void dfs (int mid ,int i , int j  ,   vector<vector<ll>> &grid , vector<vector<int>>& vis ){
  163.         vis[i][j] = 1 ;
  164.         cont ++;
  165.         if ( cont >= s ){
  166.             ans = max ( mid , ans );
  167.             flag = true;
  168.             return;
  169.         }
  170.         if ( !flag ){
  171.             for (int k = 0 ;  k < 4 ; k ++ ){
  172.                 int x = i + dxx[k];
  173.                 int y = j + dyy[k];
  174.                 if ( valid( x, y) && grid[x][y] >= mid && !vis[x][y]  ) {
  175.                     dfs(mid , x,y , grid, vis);
  176.                 }
  177.             }
  178.         }
  179. }
  180.  
  181.  
  182. void solve( ){
  183.     cin  >> s >> n >> m ;
  184.     set<int>st;
  185.     int mx = 0;
  186.     vector<vector<ll>>grid(n+5,vector<ll>(m+5,0));
  187.     vector<int > v;
  188.     for (int i =0  ; i < n;i ++ ){
  189.         for (int j = 0 ; j < m; j ++ ){
  190.             cin >> grid[i][j];
  191.             st.insert(grid[i][j]);
  192.             mx = max ( mx , grid[i][j]);
  193.         }
  194.     }
  195.     for (auto it : st ){
  196.         v.push_back((it));
  197.     }
  198.     int l = 1 , r = mx ;
  199.     while ( r >= l ){
  200.         int mid = ( r + l ) /2 ;
  201.         if ( mid <= ( *st.begin())){
  202.             l  = mid + 1 ;
  203.             ans = max ( l -1 , ans  ) ;
  204.         }
  205.         else {
  206.             vector<vector<int>>vis( n+1 , vector<int>(m));
  207.             cont = 0 ;
  208.             for (int i =0 ; i < n ; i ++ ){
  209.                 if ( flag){
  210.                     break;
  211.                 }
  212.                 for (int j = 0 ; j < m ; j ++  ){
  213.                     if ( grid[i][j] >= mid && !vis[i][j] ){
  214.                         dfs( mid ,  i , j ,grid , vis);
  215.                         if ( cont >= s ){
  216.                             flag = true;
  217.                             break;
  218.                         }
  219.                         else {
  220.                             cont = 0 ;
  221.                         }
  222.                     }
  223.                 }
  224.             }
  225.             if( flag ){
  226.                 l = mid +  1 ;
  227.             }
  228.             else {
  229.                 r = mid - 1;
  230.             }
  231.             flag = false;
  232.         }
  233.     }
  234.     cout << ans << endl;
  235.  
  236. }
  237.  
  238.  
  239. signed main( )
  240. {
  241.     //   freopen("input.txt","r",stdin);
  242.     //  freopen("output.txt","w",stdout);
  243. //#endif
  244.     fast();
  245.     int t =1;
  246.     clock_t w =clock();
  247.     // cin >> t ;
  248.     while ( t -- ){
  249.         solve();
  250.     }
  251.  
  252. // cerr << "Run time : " << ((double) (clock() - w) / CLOCKS_PER_SEC);
  253. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/GcVe6l
language:
C++ (gcc 8.3)
created:
10 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!