Submission #137638

#	Time	Username	Problem	Language	Result	Execution time	Memory
137638		SirCeness	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	65 ms	4496 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define ppair(x) "(" << x.first << ", " << x.second << ")"
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

int n, m, s, k;
vector<vector<char> > mat;
vector<vector<int> > sum;	

void put(int i, int j, int val){
	if (i >= n || j >= m) return;
	sum[max(0, i)][max(0, j)] += val;
}

int main(){
	//freopen("in", "r", stdin);
	//freopen("out", "w", stdout);

	cin >> n >> m >> s >> k;
	mat.resize(n);
	sum.resize(n);
	for (int i = 0; i < n; i++){
		mat[i].resize(m);
		sum[i].resize(m);
		for (int j = 0; j < m; j++){
			cin >> mat[i][j];
			sum[i][j] = 0;
		}
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (mat[i][j] == 'S'){
				put(i-s, j-s, 1);
				put(i-s, j+s+1, -1);
				put(i+s+1, j-s, -1);
				put(i+s+1, j+s+1, 1);
			}
		}
	}

	for (int i = 1; i < n; i++){
		for (int j = 0; j < m; j++){
			sum[i][j] += sum[i-1][j];
		}
	}

	
	for (int j = 1; j < m; j++){
		for (int i = 0; i < n; i++){
			sum[i][j] += sum[i][j-1];
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (mat[i][j] == 'M' && sum[i][j] >= k) ans++;
		}
	}
	cout << ans << 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