fork(3) download
copy 
  1. //#pragma GCC optimize("Ofast,no-stack-protector")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  3. //#pragma GCC target("avx,tune=native")
  4. // Anand Jaisingh
  5.  
  6. #include<bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef complex<double> base;
  11. typedef long double ld;
  12. typedef long long ll;
  13.  
  14. #define pb push_back
  15. #define pii pair<int,int>
  16. #define pll pair< ll , ll >
  17. #define vi vector<int>
  18. #define vvi vector< vi >
  19.  
  20. const int maxn=(int)(205);
  21. const ll mod=(ll)(1e9+7);
  22. int a[maxn];
  23. string s[maxn];
  24. int odd1[maxn][maxn],odd2[maxn][maxn],even1[maxn][maxn],even2[maxn][maxn];
  25. int vals[maxn*maxn];
  26.  
  27. int get(int i,int j,int side)
  28. {
  29.     int val1=odd1[i][j]-odd1[i][j-side]-odd1[i-side][j]+odd1[i-side][j-side];
  30.  
  31.     int val2=even2[i][j]-even2[i][j-side]-even2[i-side][j]+even2[i-side][j-side];
  32.  
  33.     int val3=odd2[i][j]-odd2[i][j-side]-odd2[i-side][j]+odd2[i-side][j-side];
  34.  
  35.     int val4=even1[i][j]-even1[i][j-side]-even1[i-side][j]+even1[i-side][j-side];
  36.  
  37.     return min(val1+val2,val3+val4);
  38. }
  39.  
  40. int main()
  41. {
  42.     ios_base::sync_with_stdio(0);cin.tie(0);
  43.  
  44.     int n,m;cin>>n>>m;
  45.  
  46.     for(int i=1;i<=n;i++)
  47.     {
  48.         cin>>s[i];
  49.  
  50.         s[i]="x"+s[i];
  51.     }
  52.  
  53.     for(int i=1;i<=n;i++)
  54.     {
  55.         int curr1=0,curr2=0;
  56.  
  57.         for(int j=1;j<=m;j++)
  58.         {
  59.             if(j%2==1 && s[i][j]!='0')
  60.             {
  61.                 curr1++;
  62.             }
  63.  
  64.             if(j%2==0 && s[i][j]!='1')
  65.             {
  66.                 curr1++;
  67.             }
  68.  
  69.             if(j%2==1 && s[i][j]!='1')
  70.             {
  71.                 curr2++;
  72.             }
  73.  
  74.             if(j%2==0 && s[i][j]!='0')
  75.             {
  76.                 curr2++;
  77.             }
  78.  
  79.             if(i%2==1)
  80.             {
  81.                 odd1[i][j]=odd1[i-1][j]+curr1;
  82.  
  83.                 odd2[i][j]=odd2[i-1][j]+curr2;
  84.  
  85.                 even1[i][j]=even1[i-1][j];
  86.  
  87.                 even2[i][j]=even2[i-1][j];
  88.             }
  89.  
  90.             else
  91.             {
  92.                 odd1[i][j]=odd1[i-1][j];
  93.  
  94.                 odd2[i][j]=odd2[i-1][j];
  95.  
  96.                 even1[i][j]=even1[i-1][j]+curr1;
  97.  
  98.                 even2[i][j]=even2[i-1][j]+curr2;
  99.             }
  100.         }
  101.     }
  102.  
  103.     for(int i=1;i<=n;i++)
  104.     {
  105.         for(int j=1;j<=m;j++)
  106.         {
  107.             int curr=min(i,j);
  108.  
  109.             for(int k=1;k<=curr;k++)
  110.             {
  111.                 int now=get(i,j,k);
  112.  
  113.                 vals[now]=max(vals[now],k);
  114.             }
  115.         }
  116.     }
  117.  
  118.     for(int i=1;i<=(n*m);i++)
  119.     {
  120.         vals[i]=max(vals[i],vals[i-1]);
  121.     }
  122.  
  123.     int q;cin>>q;
  124.  
  125.     while(q>0)
  126.     {
  127.         int x;cin>>x;
  128.  
  129.         x=min(x,n*m);
  130.  
  131.         cout<<vals[x]<<endl;
  132.  
  133.         q--;
  134.     }
  135.  
  136.     return 0;
  137. }
  138.  
Runtime error #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PEb90e
language:
C++14 (gcc 8.3)
created:
5 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!