Submission #594511

#	Time	Username	Problem	Language	Result	Execution time	Memory
594511		propransh	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	22 ms	9616 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
#define boost  ios_base::sync_with_stdio(0);
#define ll int
#define pb push_back
#define tc long long int t; cin >> t; while(t--)
#define vpll vector<pair<ll,ll>>
#define MOD 1000000007

int main(){
	
	boost;
	ll i;
	ll r,c,d,k;
	cin >> r >> c >> d >> k;
	char a[r+1][c+1];
	ll diff[r+1][c+1];
	ll pre[r+1][c+1];
	ll j;
	for(i = 1; i <= r; i++){
		for(j = 1; j <= c; j++){
			cin >> a[i][j];
			if(a[i][j] == 'S'){
				diff[i][j] = 1;
			}
			else{
				diff[i][j] = 0;
			}
		}
	}
	for(i= 0 ; i<= r; i++){
		for(j = 0; j <= c; j++){
			pre[i][j] = 0;
		}
	}
	/*for(i = 0; i <= r; i++){
		diff[i][0] = 0;
	}
	for(j = 0; j <= c; j++){
		diff[0][j] = 0;
	}
	pre[1][1] = diff[1][1];
	for(i = 1; i <= r; i++){
		pre[i][0] = pre[i-1][0] + diff[i][0]; 
	}
	for(i = 1; i < c; i++){
		pre[0][i] = pre[0][i-1] + diff[0][i];
	}*/
	for(i = 1; i <= r; i++){
		for(j = 1; j <= c; j++){
			pre[i][j] = (diff[i][j] + pre[i-1][j] + pre[i][j-1]) - pre[i-1][j-1];
			//cout << "1" <<endl;
		}
	}
	ll u,v,x,y, ans = 0;;
	/*for(i = 0; i < r; i++){
		for(j = 0; j < c; j++){
			cout << pre[i][j] << " ";
		}
		cout << endl;
	}*/
	for(i = 1; i <= r; i++){
		for(j = 1; j <= c; j++){
			if(a[i][j] == 'M'){
				u = max(1,i-d);
				v = max(1,j-d);
				x = min(r, i+d);
				y = min(c, j+d);

				ll temp = pre[x][y] - pre[u-1][y] - pre[x][v-1] + pre[u-1][v-1];
				if(temp >= k){
					ans++;
					//cout << "i " << i << " j " << j <<endl;
				}
			}
			//cout << "1" << endl; 
		}
	}
	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