Submission #1006043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006043		kebine	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	19 / 100	39 ms	57692 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));
    vector<pii> lol;
    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), j1 = max((int)1, j - d), j2 = min(m + 1, j + d);
                l[i1][j1]++, r[i2][j2]++;
                // cout << i1 << " " << i2 << " " << j1 << " " << j2 << endl;
            } else if(g[i][j] == 'M') lol.pb({i, j});
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + l[i][j];
            p2[i][j] = p2[i - 1][j] + p2[i][j - 1] - p2[i - 1][j - 1] + r[i][j];
            // cout << i << " " << j << " " << p[i][j] << " " << p2[i][j] << endl;
        }
    }
    int ans = 0;
    for(auto i : lol) {
        int a = i.fi, b = i.se;
        int tmp = p[a][b] - p2[a - 1][b] - p2[a][b - 1] + p2[a - 1][b - 1];
        if(tmp >= s) ans++;
        // cout << a << " " << b << " " << tmp << endl;
    }
    cout << ans << endl;


}   

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