fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define e '\n'
  5. #define f(i, a, b) for (ll i = a; i < b; i++)
  6. #define vll vector<ll>
  7. #define all(v) v.begin(),v.end()
  8. #define pb push_back
  9. #define i1(a) \
  10.     ll a;    \
  11.     cin >> a;
  12. #define i2(a, b) \
  13.     ll a, b;    \
  14.     cin >> a >> b;
  15. #define i3(a, b, c) \
  16.     ll a, b, c;    \
  17.     cin >> a >> b >> c;  
  18. #define is(str) \
  19.     string str; \
  20.     cin>>str;
  21. #define vi(arr, n)    \
  22.     vector<ll> arr(n); \
  23.     f(i, 0, n) cin >> arr[i];
  24. #define printv(arr,n) \
  25.     f(i,0,n) cout<<arr[i]<<' ';
  26. #define mod 1000000007
  27. #define ff first
  28. #define ss second
  29. #define mll map<ll,ll>
  30. #define R return
  31. #define light ios_base::sync_with_stdio(false); \
  32.         cin.tie(NULL); 
  33. #define B break
  34. #define C continue
  35. #define YY cout << "YES" << e
  36. #define NN cout << "NO" << e
  37. #pragma GCC optimize ("trapv")
  38.  
  39. ll Powerfun(ll x, ll y)
  40. {
  41.     ll res = 1;
  42.     while (y)
  43.     {
  44.         if (y & 1) res = (res * x) % mod;
  45.         x = (x * x) % mod; y >>= 1;
  46.     }
  47.     return res;
  48. }
  49.  
  50. ll add(ll a, ll b){
  51.     return (a%mod+b%mod)%mod;
  52. }
  53.  
  54. ll sub(ll a, ll b){
  55.     return (a%mod-b%mod+mod)%mod;
  56. }
  57.  
  58. ll mul(ll a, ll b){
  59.     return ((a%mod)*(b%mod))%mod;
  60. }
  61.  
  62. // O(bits*n^2*log(n))
  63. // bits-> 20
  64.  
  65. void solve()
  66. {
  67.     i3(n,m,r);
  68.     assert(n>=1 && n<=500 && m>=1 && m<=500); 
  69.     assert(r>=1 && r<=1e6);
  70.     ll mat[n][m];
  71.     ll bits = 20;
  72.     f(i,0,n) f(j,0,m){ 
  73.         cin>>mat[i][j]; 
  74.         assert(mat[i][j]>=1 && mat[i][j]<=1e6);
  75.     }
  76.     vector<vector<vector<ll>>> prefix(n,vector<vector<ll>>(m,vector<ll>(bits,0)));
  77.  
  78.     f(i,0,n){
  79.         f(j,0,m){
  80.             f(k,0,bits){
  81.                 if(j-1>=0){
  82.                     prefix[i][j][k]+=prefix[i][j-1][k];
  83.                 }
  84.                 if(i-1>=0){
  85.                     prefix[i][j][k]+=prefix[i-1][j][k];
  86.                 }
  87.                 if(i-1>=0 && j-1>=0){
  88.                     prefix[i][j][k]-=prefix[i-1][j-1][k];
  89.                 }
  90.                 if((1ll<<k)&mat[i][j]){
  91.                     prefix[i][j][k]++; 
  92.                 }
  93.             }
  94.         }
  95.     }
  96.     ll ans_sz = 1e9; 
  97.  
  98.     f(i,0,n){
  99.         f(j,0,m){
  100.             ll lo = 1, hi = min(n,m);
  101.             while(lo<=hi){
  102.                 ll sz = (lo+hi)/2;
  103.                 if(i-sz+1>=0 && j-sz+1>=0){
  104.                     vector<ll> cur(bits,0);
  105.                     ll val = 0; 
  106.                     f(k,0,bits){
  107.                         cur[k]+=prefix[i][j][k]; 
  108.                         if(i-sz>=0){
  109.                             cur[k]-=prefix[i-sz][j][k]; 
  110.                         }
  111.                         if(j-sz>=0){
  112.                             cur[k]-=prefix[i][j-sz][k]; 
  113.                         }
  114.                         if(i-sz>=0 && j-sz>=0){
  115.                             cur[k]+=prefix[i-sz][j-sz][k]; 
  116.                         }
  117.                         if(cur[k]){
  118.                             val|=(1ll<<k); 
  119.                         }
  120.                     }
  121.                     if(val>r){
  122.                         ans_sz = min(ans_sz,sz); 
  123.                         hi = sz-1; 
  124.                     }
  125.                     else lo = sz+1; 
  126.                 }
  127.                 else{
  128.                     hi = sz-1; 
  129.                 }
  130.             }
  131.         }
  132.     }
  133.     cout<<(ans_sz==1e9?-1:ans_sz)<<e; 
  134. }
  135.  
  136. int32_t main()
  137. {
  138.     light
  139.  
  140.     int t = 1;
  141.     // cin>>t;
  142.     while (t--)
  143.         solve();
  144.     return 0;
  145. }
  146.  
  147.  
Runtime error #stdin #stdout #stderr 0.01s 5476KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
prog: prog.cpp:68: void solve(): Assertion `n>=1 && n<=500 && m>=1 && m<=500' failed.
https://ideone.com/8D7zyR
language:
C++ (gcc 8.3)
created:
1 year 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!