Submission #1200206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200206		Hanksburger	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	17 ms	16316 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, d, k, z=0;
    cin >> n >> m >> d >> k;
    vector<pair<int, int> > v;
    int a[n+5][m+5]={};
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            char x;
            cin >> x;
            if (x=='M')
                v.push_back({i, j});
            if (x=='S')
            {
                a[min(n+1, i+d+1)][min(m+1, j+d+1)]++;
                a[min(n+1, i+d+1)][max(1, j-d)]--;
                a[max(1, i-d)][min(m+1, j+d+1)]--;
                a[max(1, i-d)][max(1, j-d)]++;
            }
        }
    }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    for (auto x:v)
        z+=a[x.first][x.second]>=k;
    cout << z;
}

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