Submission #649853

#	Time	Username	Problem	Language	Result	Execution time	Memory
649853		Ghosty_v2	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	24 ms	10672 KiB

mushrooms

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

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

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

    vector<vector<int>> arr(r+1, vector<int>(c+1, 0));
    vector<vector<int>> dp(r+1, vector<int>(c+1, 0));

    for(int i=1;i<=r;i++) {
    	for(int j=1;j<=c;j++) {
    		char s;
    		cin>>s;

    		arr[i][j] =  s;

    		dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];

    	    if (s=='S') dp[i][j]++;
    	}
    }

    int ans = 0;

    for(int i=1;i<=r;i++) {

    	for(int j=1;j<=c;j++) {

    		if (arr[i][j] != 'M') continue;
            int u = max(i-d,1);
            int v = max(j-d,1);
            int w = min(i+d,r);
            int x = min(j+d,c);    		
            int count =  dp[w][x]-dp[u-1][x]-dp[w][v-1]+dp[u-1][v-1];
            if (count>= k) ans++;

    	}

    }

    cout<<ans<<endl;

	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