Submission #785510

#	Time	Username	Problem	Language	Result	Execution time	Memory
785510		12345678	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	21 ms	18736 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

int r, c, d, k, ans;
char ch;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>r>>c>>d>>k;
    vector<pair<int, int>> s, m;
    vector<vector<int>> dp(r+5, vector<int> (c+5));
    for (int i=1; i<=r; i++)
    {
        for (int j=1; j<=c; j++)
        {
            cin>>ch;
            if (ch=='M') m.push_back({i, j});
            if (ch=='S')
            {
                dp[max(i-d, 1)][max(j-d, 1)]++;
                dp[max(i-d, 1)][min(j+d+1, c+1)]--;
                dp[min(i+d+1, r+1)][max(j-d, 1)]--;
                dp[min(i+d+1, r+1)][min(j+d+1, c+1)]++;
            }
        }
    }
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) dp[i][j]+=dp[i-1][j];
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) dp[i][j]+=dp[i][j-1];
    for (auto [x, y]:m) if (dp[x][y]>=k) ans++;
    cout<<ans;
}

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