Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include<iostream>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- #include<math.h>
- using namespace std;
- typedef unsigned int ui;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define endl "\n"
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define pb push_back
- #define pikachu push_back
- #define F first
- #define S second
- void solve() {
- }
- ll a[301][301];
- ll pref[301][301];
- void count(ll n, ll m) {
- pref[0][0] = a[0][0];
- for (ll i = 1; i < n; i++)
- pref[i][0] = pref[i - 1][0] + a[i][0];
- for (ll i = 1; i < m; i++)
- pref[0][i] = pref[0][i - 1] + a[0][i];
- for (ll i = 1; i < n; i++)
- for (ll j = 1; j < m; j++)
- pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j];
- }
- ll qq(ll x1, ll y1, ll x2, ll y2) {
- return pref[x2][y2] - (x1 ? pref[x1 - 1][y2] : 0) - (y1 ? pref[x2][y1 - 1] : 0) + (x1 && y1 ? pref[x1 - 1][y1 - 1] : 0);
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- ll t = 1;
- //cin >> t;
- //cout << fixed << setprecision(18);
- while (t--) {
- ll n, m, s, k;
- cin >> n >> m >> k >> s;
- for (ll i = 0; i < n; i++) {
- string s;
- cin >> s;
- for (ll j = 0; j < m; j++) {
- if (s[j] == '#') {
- a[i][j] = 1;
- }
- else {
- a[i][j] = 0;
- }
- }
- }
- count(n, m);
- ll ans = 0;
- ll i = 0;
- while ((i + 1) * m<s)i++;
- for (; i < n; i++) {
- if ((i + 1) * m < s)continue;
- for (ll j = s / (i + 1) - 1; j < m; j++) {
- if ((i + 1) * (j + 1) < s) {
- continue;
- }
- for (ll x = 0; x <= 0; x++) {
- if ((i - x + 1) * (j + 1) < s)
- break;
- for (ll y = 0; y <= j; y++) {
- if ((i - x + 1) * (j - y + 1) < s)
- break;
- if (qq(x, y, i, j) <= k) {
- ans++;
- }
- }
- }
- }
- }
- cout << ans << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement