fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define fast cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
  4. #define all(x) x.begin(),x.end()
  5. #define alr(x) x.rbegin(),x.rend()
  6. #define endl '\n'
  7. #define emb emplace_back
  8. #define F first
  9. #define S second
  10. #define yes cout << "YES\n"
  11. #define no cout <<"NO\n"
  12. #define pii pair< int , int>
  13. #define PI acos(-1.0)
  14. #define sz(x) (int)(x.size())
  15. #define debug cout<<"________________________________" << endl;
  16. using namespace std;
  17. int const mod = 1e9+7, N = 2e5 + 10;
  18. int n, k;
  19. int a[1000][1000];
  20. bool ok(int x)
  21. {
  22.     int pref[n+10][n+10] , b[n+10][n+10];
  23.     memset(b, 0, sizeof b);
  24.     memset(pref, 0, sizeof pref);
  25.     for(int i = 1 ; i <= n ; i ++)
  26.     {
  27.         for(int j = 1 ; j <= n ; j ++)
  28.             if(a[i][j] >=x)b[i][j]=1;
  29.             else b[i][j]=-1;
  30.     }
  31.     pref[1][1] = b[1][1];
  32.     for(int i = 2 ; i <= n ; i ++)
  33.     {
  34.         pref[1][i] += pref[1][i-1] + b[1][i];
  35.     }
  36.     for(int i = 2 ; i <= n ; i ++)
  37.     {
  38.         pref[i][1] += pref[i-1][1] + b[i][1];
  39.     }
  40.     for (int i = 2; i <= n; i++)
  41.     {
  42.         for (int j = 2; j <= n; j++)
  43.             pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + b[i][j];
  44.     }
  45.     for(int i = k ; i <= n ; i ++)
  46.     {
  47.         for(int j = k ; j <= n ; j ++)
  48.         {
  49.             int  tmp = pref[i][j] + pref[i-k][j-k] - pref[i-k][j] - pref[i][j-k];
  50.             if(tmp < (k*k)/2   )return 1;
  51.         }
  52.     }
  53.     return 0;
  54.  
  55. }
  56. void solve()
  57. {
  58.     cin >> n >> k;
  59.     int mx = 0 ;
  60.     memset(a , 0 , sizeof a);
  61.     for(int i = 1 ; i  <= n; i ++)
  62.     {
  63.         for(int j = 1 ; j <= n; j ++)
  64.         {
  65.             cin >> a[i][j];
  66.             mx = max(a[i][j], mx);
  67.         }
  68.     }
  69.     int l = 0, r = mx;
  70.     while(l+1 < r)
  71.     {
  72.         int mid = ( l + r )/2;
  73.         if(ok(mid))
  74.         {
  75.             r = mid;
  76.         }
  77.         else l = mid;
  78.  
  79.     }
  80.     cout << l << endl;
  81.  
  82. }
  83.  
  84. int32_t main()
  85. {
  86.     fast;
  87.     int test = 1;
  88.     /// cin >> test ;
  89.     while(test--)solve();
  90. }
  91.  
  92. ////////////////////////////////////////////////////
  93. //bool isPrime(ll n)
  94. //{
  95. //    if (n <= 1)return false;
  96. //    if (n <= 3)return   true;
  97. //    if (n % 2 == 0||n % 3 == 0)return false;
  98. //    for (ll i = 5; i * i <= n; i = i + 6)
  99. //        if (n % i == 0||n % (i + 2) == 0)return false;
  100. //    return true;
  101. //}
  102. //
  103. /////////////////////////////////////////////////////
  104. //
  105. /////////////////////////////////////////////////////
  106. //ll GCD(ll  a,ll  b )
  107. //{
  108. //    return b ? GCD(b, a % b ) : a ;
  109. //}
  110. /////////////////////////////////////////////////////
  111. //ll LCst(ll a, ll b)
  112. //{
  113. //    return (a / GCD(a, b)) * b;
  114. //}
  115.  
  116. //ll  po(ll  x, ll os)
  117. //{
  118. //    if( os == 0 )
  119. //        return 1;
  120. //    ll z = po(x,os/2);
  121. //    if( os&1 )
  122. //        return z*z%stod*x%stod;
  123. //
  124. //    return z*z%stod;
  125. //}
  126. ////////////////////////////////////////////////////
  127. //ll exEuclid(ll a, ll b, ll& x, ll& y)
  128. //{
  129. //    if (b==0)
  130. //    {
  131. //        x=1;
  132. //        y=0;
  133. //        return a;
  134. //    }
  135. //    ll x1,y1;
  136. //    ll d=exEuclid(b,a%b,x1,y1);
  137. //    x=y1;
  138. //    y=x1-y1*(a/b);
  139. //    return d;
  140. //}
  141. /////////////////////////////////////////////////////////
  142. //bool cmp(const pair<int, int>& a, const pair<int, int>& b)
  143. //{
  144. //    if (a.first != b.first)return a.first > b.first;
  145. //    return a.second > b.second;
  146. //}
  147. /////////////////////////////////////////////////////////
  148. ///// indexed set
  149. /////#include <ext/pb_ds/assoc_container.hpp>
  150. /////#include <ext/pb_ds/tree_policy.hpp>
  151. /////#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  152. /////using nastespace __gnu_pbds;
  153. /////////////////////////////////////////////////////////
  154.  
Success #stdin #stdout 0.01s 11324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/qbye3V
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!