Submission #1328240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328240		ninstroyer	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	38 / 100	15 ms	11448 KiB

mushrooms

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

int n,m,d,k;
vector<pair<int,int>> pos;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>d>>k;
    vector<vector<char>> mat(n+1,vector<char>(m+1));
    vector<vector<int>> pref(n+1,vector<int>(m+1,0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>mat[i][j];
            if(mat[i][j] == 'M') pos.push_back({i+d,j+d});
            pref[i][j] = (mat[i][j]=='S') + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
        }
    }
    int res = 0;
    for(auto [i,j] : pos)
    {
        int r1 = min(i,n);
        int c1 = min(j,m);
        int r2 = max(r1-2*d,1);
        int c2 = max(c1-2*d,1);
        int cnt = pref[r1][c1] - pref[r2-1][c1] - pref[r1][c2-1] + pref[r2-1][c2-1];
        if(cnt >= k) res++;
    }
    cout<<res;
}

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