Submission #666747

#	Time	Username	Problem	Language	Result	Execution time	Memory
666747		Ai7081	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	19 ms	19580 KiB

mushrooms

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

int r, c, d, k, out;
string s;
vector<vector<int>> sum;
vector<pair<int, int>> vp;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> r >> c >> d >> k;
    sum.assign(r+5, vector<int>(c+5, 0));// = vector<int>(r+5, vector<int>(c+5));
    for (int i=0; i<r; i++) {
        cin >> s;
        for (int j=0; j<c; j++) {
            if (s[j] == 'S') {
                int x0=max(0, i+1-d), x1=min(r+1, i+1+d+1), y0=max(0, j+1-d), y1=min(c+1, j+1+d+1);
                sum[x0][y0]++;
                sum[x0][y1]--;
                sum[x1][y0]--;
                sum[x1][y1]++;
            }
            else if (s[j] == 'M') vp.push_back({i, j});
        }
    }
    // for (int i=0; i<=r+1; i++) {for (int j=0; j<=c+1; j++) cout << sum[i][j] << ' '; cout << endl;}
    for (int i=1; i<=r; i++) sum[i][0]+=sum[i-1][0];
    for (int j=1; j<=c; j++) sum[0][j]+=sum[0][j-1];
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    for (auto [x, y] : vp) if (sum[x+1][y+1] >= k) out++;
    // for (int i=1; i<=r; i++) {for (int j=1; j<=c; j++) cout << sum[i][j] << ' '; cout << endl;}
    cout << out;
    return 0;
}

/*
5 5 1 1
....M
.M...
..S..
.S...
...M.

1 8 5 2
SM..MM.S

5 5 2 2
....M
.M...
..S..
.S...
...M.
*/

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