oj.uz

Submission #373768

# Submission time Handle Problem Language Result Execution time Memory
373768 2021-03-05T17:21:22 Z guka415 Collecting Mushrooms (NOI18_collectmushrooms) C++14
100 / 100
 16 ms 7008 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 372 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2284 KB Output is correct
2 Correct 4 ms 2412 KB Output is correct
3 Correct 4 ms 2796 KB Output is correct
4 Correct 3 ms 2412 KB Output is correct
5 Correct 4 ms 2540 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 10 ms 5888 KB Output is correct
3 Correct 9 ms 5888 KB Output is correct
4 Correct 9 ms 6016 KB Output is correct
5 Correct 9 ms 5888 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 372 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 3 ms 2284 KB Output is correct
17 Correct 4 ms 2412 KB Output is correct
18 Correct 4 ms 2796 KB Output is correct
19 Correct 3 ms 2412 KB Output is correct
20 Correct 4 ms 2540 KB Output is correct
21 Correct 8 ms 5888 KB Output is correct
22 Correct 10 ms 5888 KB Output is correct
23 Correct 9 ms 5888 KB Output is correct
24 Correct 9 ms 6016 KB Output is correct
25 Correct 9 ms 5888 KB Output is correct
26 Correct 16 ms 7008 KB Output is correct
27 Correct 9 ms 5228 KB Output is correct
28 Correct 8 ms 5228 KB Output is correct
29 Correct 8 ms 5228 KB Output is correct
30 Correct 13 ms 6372 KB Output is correct