oj.uz

Submission #674870

# Submission time Handle Problem Language Result Execution time Memory
674870 2022-12-26T12:15:03 Z QwertyPi Collecting Mushrooms (NOI18_collectmushrooms) C++14
38 / 100
 35 ms 3220 KB 
#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[r2 * 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 316 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3172 KB Output is correct
2 Correct 35 ms 3172 KB Output is correct
3 Correct 33 ms 3220 KB Output is correct
4 Correct 31 ms 3184 KB Output is correct
5 Correct 30 ms 3148 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -