Submission #572426

#	Time	Username	Problem	Language	Result	Execution time	Memory
572426		MODDI	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	35 ms	5676 KiB

mushrooms

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int r, c, d, k;
int main(){
	cin>>r>>c>>d>>k;
	char mat[r+1][c+1];
	int pref[r+1][c+1];
	memset(pref, 0, sizeof(pref));
	for(int i = 1; i <= r; i++){
      for(int j = 1; j <=c; j++){
          cin >> mat[i][j];
          pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (mat[i][j] == 'S');
      }
  	}
	ll rez=  0;
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= c; j++){
			if(mat[i][j] == 'M'){
				 int a = max(i - d, 1),b = max(j - d, 1), x = min(i + d, r), y = min(j + d, c);
	          	int cr = pref[x][y] - pref[x][b- 1] - pref[a - 1][y] + pref[a - 1][b - 1];
	          	rez += (cr >= k);
			}
		}
	}
	cout<<rez<<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