Submission #1139899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139899		grizo	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	6 ms	6876 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(v)                                                                 \
    cerr << "Line(" << __LINE__ << ") -> " << #v << " = " ; 
#define dbx(x) debug(x); cerr << x << "\n";
#define dbg(x) debug(x); cerr << "{ "; for(auto &e : x) cerr << e << ", "; cerr << "} \n";
#define log(x) (31^__builtin_clz(x))

const int N = 1e6+10, MOD = 1e9+7;

void solve(){

    int n, m, d, k; cin >> n >> m >> d >> k;
    vector<string> s(n);
    for(int i = 0 ; i < n ; i ++)cin >> s[i];

    vector<vector<int>> pref(n+1, vector<int>(m+1));
    // build the prefix sum array
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pref[i][j] = (s[i-1][j-1] == 'S') + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    auto query = [&](int x1, int y1, int x2, int y2){
        x1 = max(x1, 1); y1 = max(y1, 1);
        x2 = min(x2, n); y2 = min(y2, m);
        return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
    };

    int ans = 0;
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < m ; j ++){
            if(s[i][j] == 'M'){
                if(query(i+1-d, j+1-d, i+1+d, j+1+d) >= k)ans++;
            }
        }
    }
    cout << ans << "\n";

}
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // freopen("king2.in", "r", stdin);
    // freopen("king2.out", "w", stdout);

    int tc = 1; // cin >> tc;
    for(int t = 1 ; t <= tc ; t ++){
        solve();
    }
 
    return 0;
}
 
/*

*/

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