제출 #1328243

#제출 시각아이디문제언어결과실행 시간메모리
1328243ninstroyerCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
14 ms11504 KiB
#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 cnt = pref[min(i,n)][min(j,m)] - pref[max(i-2*d-1,0)][min(j,m)] - pref[min(i,n)][max(j-2*d-1,0)] + pref[max(i-2*d-1,0)][max(j-2*d-1,0)];
        if(cnt >= k) res++;
    }
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...