Submission #1006079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006079		devariaota	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	34 ms	48732 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
bool ckmin(int& a, int b){return b < a ? a = b, 1 : 0;}
bool ckmax(int& a, int b){return b > a ? a = b, 1 : 0;}
const int N = 2e5 + 5, mod = 1e9 + 7;
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m, d, s; cin >> n >> m >> d >> s;
    int p[n + 2][m + 2], p2[n + 2][m + 2];
    char g[n + 2][m + 2];
    int l[n + 2][m + 2], r[n + 2][m + 2];
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    memset(p, 0, sizeof(p));
    memset(p2, 0, sizeof(p2));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if(g[i][j] == 'S') {
                int i1 = max((int)1, i - d), i2 = min(n + 1, i + d + 1), j1 = max((int)1, j - d), j2 = min(m + 1, j + d + 1);
                l[i1][j1]++, l[i2][j1]--, l[i1][j2]--, l[i2][j2]++;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            l[i][j] = l[i - 1][j] + l[i][j - 1] - l[i - 1][j - 1] + l[i][j];
            if(g[i][j] == 'M' && l[i][j] >= s) ans++;
        }
    }
    cout << ans << endl;
    


}   

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