Submission #892930

#	Time	Username	Problem	Language	Result	Execution time	Memory
892930		votranngocvy	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	18 ms	17008 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

vector<vector<char>>a;
vector<vector<int>>pre;

int sum(int x,int y,int u,int v) {
    return pre[u][v] - pre[x - 1][v] - pre[u][y - 1] + pre[x - 1][y - 1];
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m,d,k;
    cin >> n >> m >> d >> k;
    a.assign(n + 5,vector<char>(m + 5));
    pre.assign(n + 5,vector<int>(m + 5,0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') pre[i][j]++;
            pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 'M' && sum(max(1,i - d),max(1,j - d),min(n,i + d),min(m,j + d)) >= k)
                ans++;
    cout << ans << "\n";
}

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