Advertisement
ivnikkk

Untitled

Dec 25th, 2021
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.55 KB | None | 0 0
  1. #include <vector>
  2. #include<iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include<math.h>
  18. using namespace std;
  19. typedef unsigned int ui;
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. #define endl "\n"
  24. #define all(a) a.begin(), a.end()
  25. #define allr(a) a.rbegin(), a.rend()
  26. #define pb push_back
  27. #define pikachu push_back
  28. #define F first
  29. #define S second
  30.  
  31. void solve() {
  32.  
  33. }
  34. ll a[301][301];
  35. ll pref[301][301];
  36. void count(ll n, ll m) {
  37. pref[0][0] = a[0][0];
  38. for (ll i = 1; i < n; i++)
  39. pref[i][0] = pref[i - 1][0] + a[i][0];
  40. for (ll i = 1; i < m; i++)
  41. pref[0][i] = pref[0][i - 1] + a[0][i];
  42. for (ll i = 1; i < n; i++)
  43. for (ll j = 1; j < m; j++)
  44. pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j];
  45. }
  46. ll qq(ll x1, ll y1, ll x2, ll y2) {
  47. return pref[x2][y2] - (x1 ? pref[x1 - 1][y2] : 0) - (y1 ? pref[x2][y1 - 1] : 0) + (x1 && y1 ? pref[x1 - 1][y1 - 1] : 0);
  48. }
  49. signed main() {
  50. ios_base::sync_with_stdio(false);
  51. cin.tie(nullptr);
  52. ll t = 1;
  53. //cin >> t;
  54. //cout << fixed << setprecision(18);
  55. while (t--) {
  56. ll n, m, s, k;
  57. cin >> n >> m >> k >> s;
  58. for (ll i = 0; i < n; i++) {
  59. string s;
  60. cin >> s;
  61. for (ll j = 0; j < m; j++) {
  62. if (s[j] == '#') {
  63. a[i][j] = 1;
  64. }
  65. else {
  66. a[i][j] = 0;
  67. }
  68. }
  69. }
  70. count(n, m);
  71. ll ans = 0;
  72. for (ll i = 0; i < n; i++) {
  73. if ((i + 1) * m < s)continue;
  74. for (ll j = 0; j < m; j++) {
  75. if ((i + 1) * (j + 1) < s) {
  76. continue;
  77. }
  78. for (ll x = 0; x <= i; x++) {
  79. if ((i - x + 1) * (j + 1) < s)break;
  80. for (ll y = 0; y <= j; y++) {
  81. if ((i - x + 1) * (j - y + 1) < s)break;;
  82. if (qq(x, y, i, j) <= k) {
  83. ans++;
  84. }
  85. }
  86. }
  87. }
  88. }
  89. cout << ans << endl;
  90. }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement