fork(2) download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. string s[51];
  25. int dp[51][40001];
  26. int m, n;
  27. void calcdp()
  28. {
  29. 	for(int i = 1; i <= m; i++)
  30. 	{
  31. 		for(int j = 1; j <= n; j++)
  32. 		{
  33. 			if(s[i-1][j-1] == '1') dp[i][j] = 1;
  34. 			dp[i][j] += dp[i-1][j];
  35. 			dp[i][j] += dp[i][j-1];
  36. 			dp[i][j] -= dp[i-1][j-1];
  37. 		}
  38. 	}
  39. }
  40.  
  41. int calc(int x1, int y1, int x2, int y2)
  42. {
  43. 	return (dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);
  44. }
  45.  
  46. int solve(int x1, int y1, int mx)
  47. {
  48. 	int cnt = 0;
  49. 	for(int i = x1; i <= m; i++)
  50. 	{
  51. 		int lo = y1; int hi = n;
  52. 		int ans = lo-1;
  53. 		while(lo <= hi)
  54. 		{
  55. 			int mid = (lo+hi)>>1;
  56. 			int cal = calc(x1, y1, i, mid);
  57. 			if(cal > mx)
  58. 			{
  59. 				hi = mid - 1;
  60. 			}	
  61. 			else
  62. 			{
  63. 				lo = mid + 1;
  64. 				ans = mid;
  65. 			}
  66. 		}
  67. 		cnt += (ans - y1 + 1);
  68. 	}	
  69. 	return cnt;
  70. }
  71.  
  72. int main()
  73. {
  74. 	ios_base::sync_with_stdio(0); cin.tie(0);
  75. 	cin>>m>>n;
  76. 	for(int i = 0; i < m; i++)
  77. 	{
  78. 		cin >> s[i];
  79. 	}
  80. 	calcdp();
  81. 	int l, r; cin>>l>>r;
  82. 	ll ans = 0;
  83. 	for(int i = 1; i <= m; i++)
  84. 	{
  85. 		for(int j = 1; j <= n; j++)
  86. 		{
  87. 			ans += solve(i, j, r);
  88. 			if(l > 0) ans -= solve(i, j, l - 1);
  89. 		}
  90. 	}
  91. 	cout << ans;
  92. }
  93.  
Success #stdin #stdout 0s 11440KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Ibjh4a
language:
C++14 (gcc 8.3)
created:
8 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!