fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN=1e6+5, mod=1e9+7;
  11.  
  12. int n, m, good[maxN];
  13. vector<vector<int>>a, pref;
  14. vector<int>snt;
  15.  
  16. void sieve()
  17. {
  18.     for(int i=2; i<=1e6; i+=1) good[i]=1;
  19.     for(int i=2; i<=1e6; i+=1)
  20.     {
  21.         if(good[i])
  22.         {
  23.             for(int j=i*2; j<=1e6; j+=i) good[j]=0;
  24.         }
  25.     }
  26.     for(int i=2; i<=1e6; i+=1)
  27.     {
  28.         if(good[i]) snt.push_back(i);
  29.     }
  30. }
  31.  
  32. void solve1()
  33. {
  34.     for(int i=1; i<=n; i+=1)
  35.     {
  36.         for(int j=1; j<=m; j+=1) a[i][j]=good[a[i][j]];
  37.     }
  38.     for(int i=1; i<=n; i+=1)
  39.     {
  40.         for(int j=1; j<=m; j+=1)
  41.         {
  42.             pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
  43.         }
  44.     }
  45.     if(n>m) swap(n,m);
  46.     int ans=0;
  47.     for(int mid=0; mid<=n; mid+=1)
  48.     {
  49.         bool check=0;
  50.         for(int i=1; i<=n; i+=1)
  51.         {
  52.             for(int j=1; j<=m; j+=1)
  53.             {
  54.                 if(i+mid-1>n || j+mid-1>m) continue;
  55.                 int xet=pref[i+mid-1][j+mid-1]+pref[i-1][j-1]-pref[i+mid-1][j-1]-pref[i-1][j+mid-1];
  56.                 if(xet>=mid*mid-1) ans=max(ans, mid*mid);
  57.             }
  58.         }
  59.     }
  60.     cout<<ans<<'\n';
  61. }
  62.  
  63. void solve()
  64. {
  65.     for(int i=1; i<=n; i+=1)
  66.     {
  67.         for(int j=1; j<=m; j+=1) a[i][j]=good[a[i][j]];
  68.     }
  69.     for(int i=1; i<=n; i+=1)
  70.     {
  71.         for(int j=1; j<=m; j+=1)
  72.         {
  73.             pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
  74.         }
  75.     }
  76. //    for(int i=1; i<=n; i+=1)
  77. //    {
  78. //        for(int j=1; j<=m; j+=1) cout<<a[i][j]<<" "; cout<<'\n';
  79. //    }
  80.     if(n>m) swap(n,m);
  81.     int l=-1, r=n, ans=0;
  82.     while(r-l>1)
  83.     {
  84.         int mid=(l+r)>>1;
  85.         bool check=0;
  86.         for(int i=1; i<=n; i+=1)
  87.         {
  88.             for(int j=1; j<=m; j+=1)
  89.             {
  90.                 if(i+mid-1>n || j+mid-1>m) continue;
  91.                 int xet=pref[i+mid-1][j+mid-1]+pref[i-1][j-1]-pref[i+mid-1][j-1]-pref[i-1][j+mid-1];
  92.                 if(xet>=mid*mid-1) check=1;
  93.             }
  94.         }
  95. //       cout<<mid<<" "<<check<<'\n';
  96.         if(check) l=mid;
  97.         else r=mid;
  98.     }
  99.     bool check=0;
  100.     for(int i=1; i<=n; i+=1)
  101.     {
  102.         for(int j=1; j<=m; j+=1)
  103.         {
  104.             if(i+r-1>n || j+r-1>m) continue;
  105.             int xet=pref[i+r-1][j+r-1]+pref[i-1][j-1]-pref[i+r-1][j-1]-pref[i-1][j+r-1];
  106.             if(xet>=r*r-1) check=1;
  107.         }
  108.     }
  109.     if(check) cout<<r*r<<'\n';
  110.     else cout<<l*l<<'\n';
  111. }
  112.  
  113. int32_t main()
  114. {
  115.     ios_base::sync_with_stdio(0); cin.tie(0);
  116.     sieve();
  117.     cin>>n>>m;
  118.     a.assign(n+1, vector<int>());
  119.     pref.assign(n+1, vector<int>());
  120.     for(int i=1; i<=n; i+=1)
  121.     {
  122.         a[i].push_back(0);
  123.         for(int j=1; j<=m; j+=1)
  124.         {
  125.             int x; cin>>x;
  126.             a[i].push_back(x);
  127.         }
  128.     }
  129.     for(int i=0; i<=n; i+=1) pref[i].assign(m+1, 0);
  130.     if(n<=300 && m<=300) solve1();
  131.     else solve();
  132. }
  133.  
Success #stdin #stdout 0.02s 11940KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/YfSCC3
language:
C++14 (gcc 8.3)
created:
6 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!