Submission #1309489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309489		thecrazycandy	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	18 ms	20504 KiB

mushrooms

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define ll long long
#define sped_up ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define S second
#define F first
const ll INF = (ll)1e9 + 1, INFL = (ll)1e18 + 1;
const ll mod = (ll)1e9 + 7, MAXN = (ll)1e5 + 1;
int main() {
    sped_up;
    ll n, m, d, k;
    cin >> n >> m >> d >> k;
    ll cnt = 0;
    ll a[n + 2][m + 2] = {};
    vector <pair <ll, ll>> v;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            char c;
            cin >> c;
            if ('S' == c) {
                a[max(1ll, i - d)][max(1ll, j - d)]++, a[max(1ll, i - d)][min(m, j + d) + 1]--;
                a[min(n, i + d) + 1][max(1ll, j - d)]--, a[min(n, i + d) + 1][min(m, j + d) + 1]++;
            }
            if ('M' == c) v.pb({i, j});
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] += a[i][j - 1];
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            a[i][j] += a[i - 1][j];
        }
    }
    for (auto i : v) cnt += (a[i.F][i.S] >= k);
    cout << cnt;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21