Submission #1168829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168829		jadai007	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	10 ms	9032 KiB

mushrooms

/*
    Author : detective conan
    Problem : NOI18_collecting mushroom
    Created : 18/03/2025 10:43 UTC+7
*/
#include <bits/stdc++.h>
#define int long long
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define rep(i, s, t) for(int i = s; i >= t; --i)
#define DB(n, s) cout << n << s
#define ANS(n, s) DB(n, s)
#define mod (int)(1e9 + 7)
#define HAVE_TESTCASE false
#define pb push_back
#define eb emplace_back
#define em emplace
#define ph push
#define conan cin.tie(nullptr)->sync_with_stdio(false);

using namespace std;
using u32 = unsigned;
using i64 = int64_t;
using u64 = unsigned i64;

const int MAX_N = 3e5 + 20;
int R, C, D, K, ans;

void solve(){
    cin >> R >> C >> D >> K;
    char mp[R + 1][C + 1] = {{'-'}};
    int dp[R + 1][C + 1] = {{0}};
    FOR(i, 1, R) FOR(j, 1, C) cin >> mp[i][j], dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (mp[i][j] == 'S');
    FOR(i, 1, R){
        FOR(j, 1, C){
            if(mp[i][j] == 'M'){
                int sum = dp[min(i + D, R)][min(j + D, C)] - dp[max(i - D - 1ll, 0ll)][min(j + D, C)] - dp[min(i + D, R)][max(j - D - 1ll, 0ll)] + dp[max(i - D - 1ll, 0ll)][max(j - D - 1ll, 0ll)];
                if(sum >= K) ans++;
            }
        }
    }
    ANS(ans, '\n');
}

int32_t main(){
    conan;
    int t = 1;
    if(HAVE_TESTCASE) cin >> t;
    while(t--) solve();
}

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