Submission #674872

#	Time	Username	Problem	Language	Result	Execution time	Memory
674872		QwertyPi	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	32 ms	3152 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 11;
char a[MAXN];
int dp[MAXN];

int r, c, d, k;
int id(int i, int j){
	return i * c + j;
}

int main(){
	cin >> r >> c >> d >> k;
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cin >> a[i * c + j];
		}
	}
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(a[i * c + j] == 'S'){
				int r1 = max(0, i - d), r2 = min(r - 1, i + d);
				int c1 = max(0, j - d), c2 = min(c - 1, j + d);
				dp[r1 * c + c1]++;
				if(r2 != r - 1) dp[(r2 + 1) * c + c1]--;
				if(c2 != c - 1) dp[r1 * c + (c2 + 1)]--;
				if(r2 != r - 1 && c2 != c - 1) dp[(r2 + 1) * c + (c2 + 1)]++;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			if(i > 0 && j > 0) dp[i * c + j] -= dp[(i - 1) * c + j - 1];
			if(i > 0) dp[i * c + j] += dp[(i - 1) * c + j];
			if(j > 0) dp[i * c + j] += dp[i * c + j - 1];
			if(a[i * c + j] == 'M' && dp[i * c + 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