fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<int,int>
  4. #define all(x) x.begin(),x.end()
  5.  
  6. int n,m;
  7. vector<pair<int,int> > p1,p2;
  8.  
  9. void solve(int ref,vector<vector<int> > &mat){
  10.  
  11.   int mm[min(n,m)+7];
  12.   vector<pii> pp;
  13.   int dp[n][m];
  14.   memset(dp,0,sizeof(dp));
  15.  
  16.   for(int i=0;i<n;i++){
  17.   	int tr = ref;
  18.   	for(int j=0;j<m;j++){
  19. 		if(mat[i][j]!=tr) dp[i][j] = 1;
  20. 		tr = 1 - tr;
  21.   	}
  22.   } 	
  23.  
  24.    for(int i=1;i<n;i++) dp[i][0]+=dp[i-1][0]; 
  25.    for(int j=1;j<m;j++) dp[0][j]+=dp[0][j-1]; 
  26.  
  27.    for(int i=1;i<n;i++){
  28.  
  29.    	 for(int j=1;j<m;j++) dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];  
  30.  
  31.    } 
  32.  
  33.    for(int k=1;k<=min(n,m);k++) mm[k] = INT_MAX;
  34.  
  35.     for(int k=1;k<=min(n,m);k++){
  36.  
  37. 	   for(int i=0;i<n;i++){
  38.  
  39. 		for(int j=0;j<m;j++){
  40.  
  41. 	  	  if(i-k>=0 && j-k>=0){
  42.  
  43. 	  	  	int cost = dp[i][j] - dp[i-k][j] - dp[i][j-k] + dp[i-k][j-k];
  44. 	  	  	mm[k] = min(mm[k],cost);
  45. 	  	  }	
  46.  
  47. 		}	
  48.  
  49. 	 }  
  50.  
  51.     }	
  52.  
  53. 	 //Main part of the code	
  54. 	 vector<pair<int,int> > px;
  55. 	 for(int k=1;k<=min(n,m);k++) px.push_back(make_pair(mm[k],k)); 	
  56. 	 sort(all(px));
  57. 	 pp[0].first = 0;
  58. 	 for(int i=1;i<px.size();i++) px[i].second  = max(px[i].second,px[i-1].second); 
  59.      if(ref) p1 = px;
  60.      else p2 = px;
  61. }
  62.  
  63.  
  64. int main() {
  65.  
  66. 	ios_base::sync_with_stdio(false);
  67. 	cin.tie(0); cout.tie(0);
  68.  
  69. 	cin>>n>>m;
  70. 	vector<vector<int> > mat(n,vector<int>(m,0));
  71.  
  72. 	for(int i=0;i<n;i++){
  73. 	  for(int j=0;j<m;j++) cin>>mat[i][j];	
  74. 	}
  75.  
  76. 	solve(0,mat);
  77. 	solve(1,mat);
  78.  
  79. 	int q,x;
  80. 	cin>>q;
  81. 	while(q-->0)
  82. 	{
  83.  
  84. 	  cin>>x;	
  85. 	  int ii1 = upper_bound(all(p1),make_pair(x,INT_MAX)) - p1.begin();
  86. 	  int ii2 = upper_bound(all(p2),make_pair(x,INT_MAX)) - p2.begin();
  87. 	  int mx = 1;
  88. 	  mx = max(mx,max(p1[ii1-1].second,p2[ii2-1].second));
  89. 	  cout<<mx<<'\n';
  90. 	}
  91.  
  92. 	return 0;
  93. }
Runtime error #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
8 8
00101010
00010101
10101010
01010101
10101010
01010101
10101010
01010101
4
1 2 0 1001
stdout
copy 
Standard output is empty
https://ideone.com/Ek7ODT
language:
C++14 (gcc 8.3)
created:
3 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!