Submission #393030

#	Time	Username	Problem	Language	Result	Execution time	Memory
393030		pr0gramm3r	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	16 ms	7116 KiB

mushrooms

# include <bits/stdc++.h>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;
# define ll                 long long
# define flp(i, n)          for (int i = 0; i < n; i++)
# define endl               "\n"
# define TEST               int t; cin >> t; while (t--)
# define MOD                1000000007
# define all(x)             x.begin(), x.end()
# define print(x)           for (auto i : x) cout << i << " ";\
                            cout << endl;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

signed main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);

    int r, c, d, k;
    cin >> r >> c >> d >> k;

    char arr[r + 1][c + 1];
    for (int i = 1; i <= r; i++) for (int j = 1; j <= c;j++) cin >> arr[i][j];

    int dp[r + 2][c + 2];
    memset(dp, 0, sizeof dp);

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (arr[i][j] == 'S') {
                dp[max(1, i - d)][max(1, j - d)]++;
                dp[min(r,i + d) + 1][min(c,j + d) + 1]++;
                dp[min(r,i + d) + 1][max(1, j - d)]--;
                dp[max(1, i - d)][min(c, j + d) + 1]--;
            }
        }
    }

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    }

    int cnt = 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (arr[i][j] == 'M') if (dp[i][j] >= k) cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Compilation message (stderr)

mushrooms.cpp:21: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   21 | #pragma GCC optimization ("O3")
      | 
mushrooms.cpp:22: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   22 | #pragma GCC optimization ("unroll-loops")
      |

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