Submission #1238359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238359		paullyboy111	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	60 / 100	2095 ms	3792 KiB

mushrooms

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int R, C, D, K;
    cin >> R >> C >> D >> K;
    
    vector<string> grid(R);
    for (int i = 0; i < R; i++) {
        cin >> grid[i];
    }
    
    // Find all mushrooms and sprinklers
    vector<pair<int, int>> mushrooms, sprinklers;
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == 'M') {
                mushrooms.push_back({i, j});
            } else if (grid[i][j] == 'S') {
                sprinklers.push_back({i, j});
            }
        }
    }
    
    int harvestable = 0;
    
    // For each mushroom, count how many sprinklers can water it
    for (auto& mushroom : mushrooms) {
        int count = 0;
        int mx = mushroom.first, my = mushroom.second;
        
        for (auto& sprinkler : sprinklers) {
            int sx = sprinkler.first, sy = sprinkler.second;
            
            // Chebyshev distance: max(|x1-x2|, |y1-y2|)
            int distance = max(abs(sx - mx), abs(sy - my));
            
            if (distance <= D) {
                count++;
            }
        }
        
        // Check if this mushroom is harvestable
        if (count >= K) {
            harvestable++;
        }
    }
    
    cout << harvestable << endl;
    
    return 0;
}

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