Submission #373768

#	Time	Username	Problem	Language	Result	Execution time	Memory
373768		guka415	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	16 ms	7008 KiB

mushrooms

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define ff first
#define ss second 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


int n, m, d, k;
vector<string> board;
vector<vector<ll>> pre;

int query(int _i, int _j) {
	int i1 = max(0, _i - d), j1 = max(0, _j - d), i2 = min(n - 1, _i + d), j2 = min(m - 1, _j + d);
	if (i1 > i2 || j1 > j2)
		return 0;
	if (i1 && j1)
		return pre[i2][j2] + pre[i1 - 1][j1 - 1] - pre[i1 - 1][j2] - pre[i2][j1 - 1];
	else if (!i1 && !j1)
		return pre[i2][j2];
	else if (!i1)
		return pre[i2][j2] - pre[i2][j1 - 1];
	else
		return pre[i2][j2] - pre[i1 - 1][j2];
}


int main() {
	fast;
	cin >> n >> m >> d >> k;
	pre.resize(n);
	foru(i, 0, n) {
		pre[i].assign(m, 0);
		string s;
		cin >> s;
		board.pb(s);
	}
	foru(i, 0, n) {
		foru(j, 0, m) {
			if (!i && !j)pre[i][j] = (board[i][j] == 'S');
			else if (!i)pre[i][j] = (pre[i][j - 1] + (board[i][j] == 'S'));
			else if (!j)pre[i][j] = (pre[i - 1][j] + (board[i][j] == 'S'));
			else pre[i][j] = (pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + (board[i][j] == 'S'));
		}
	}
	int ret = 0;
	foru(i, 0, n) {
		foru(j, 0, m) {
			if (board[i][j] == 'M')
				ret += (query(i, j) >= k);
		}
	}
	cout << ret;
	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