fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std; 
  4. const int MOD=1e9 +7 ; 
  5.  
  6. char bar[1005][1005]; 
  7. int dp[2][2005]; 
  8. int white[1005]; 
  9. int sum[1005];
  10. int main()
  11. {
  12.     memset(white,0,sizeof(white));
  13.  
  14. 	int n,m,x,y; 
  15. 	cin>>n>>m>>x>>y; 
  16.  
  17. 	for(int i=0;i<n;i++){
  18. 		for(int j=0;j<m;j++){
  19. 			cin>>bar[i][j];
  20. 			if(bar[i][j]=='.') white[j]++;   
  21. 		}
  22. 	}
  23.  
  24. memset(&dp,1000000,sizeof(dp));
  25.  dp[0][0]=0; 
  26.  dp[1][0]=0; 
  27.  sum[0]=0;
  28. for(int i=0;i<=m;i++) sum[i+1]=sum[i]+white[i];
  29.  
  30. for(int i=0;i<m;i++){
  31. 	for(int j=x;j<=y;j++){
  32. 		if(i+j>m){break;}
  33. 		dp[0][i+j]=min(dp[0][i+j],dp[1][i]+sum[i+j]-sum[i]);
  34. 		dp[1][i+j]=min(dp[1][i+j],dp[0][i]+(j)*n-(sum[i+j]-sum[i])); 
  35. 	}	
  36. }
  37.  
  38.  
  39. cout<<min(dp[0][m],dp[1][m])<<endl;;
  40.  
  41. return 0;   
  42. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/6LaZPh
language:
C++ (gcc 8.3)
created:
4 years 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!