Submission #970445

#	Time	Username	Problem	Language	Result	Execution time	Memory
970445		NoMercy	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	28 ms	13616 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
 
    
int TIME = clock();
 
#define file \
            freopen("in.txt" , "r" , stdin); \
            freopen("out.txt" , "w" , stdout);
 
#define int long long 
 
void test_case () {
    int n , m , d , k;
    cin >> n >> m >> d >> k;
    char c[n + 1][m + 1];
    int pre[n + 2][m + 2];
    for (int i = 0;i <= n + 1;i ++) {
        for (int j = 0;j <= m + 1;j ++) {
            pre[i][j] = 0;
        }
    }
    for (int i = 1;i <= n;i ++) {
        for (int j = 1;j <= m;j ++) {
            cin >> c[i][j];
        }
    }
    for (int i = 1;i <= n;i ++) {
        for (int j = 1;j <= m;j ++) {
            assert(c[i][j] == 'S' || c[i][j] == 'M' || c[i][j] == '.');
            if (c[i][j] == 'S') {
                pre[max(0LL , i - d)][max(0LL , j - d)] ++;
                pre[min(n + 1 , i + d + 1)][min(m + 1 , j + d + 1)] ++;
                pre[min(n + 1 , i + d + 1)][max(0LL , j - d)] --;
                pre[max(0LL , i - d)][min(m + 1 , j + d + 1)] --;
            }
        }
    }
    for (int i = 0;i <= n;i ++) {
        for (int j = 0;j <= m;j ++) {
            if (i > 0) {
                pre[i][j] += pre[i - 1][j];
            }
            if (j > 0) {
                pre[i][j] += pre[i][j - 1];
            }
            if (i > 0 && j > 0) {
                pre[i][j] -= pre[i - 1][j - 1];
            }
        }
    }
    
    int res = 0;
    for (int i = 1;i <= n;i ++) {
        for (int j = 1;j <= m;j ++) {
            res += bool(c[i][j] == 'M' && pre[i][j] >= k);
        }
    }
    cout << res << "\n";
}
 
/*
 
 
.......
.......
.......
.......
.......
 
*/
 
int32_t main () {
 
    ///    file
    
 
    int t = 1;
    // cin >> t;
 
    while (t --) {
        test_case();
    }
 
    return 0;
}

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