oj.uz

Submission #506320

# Submission time Handle Problem Language Result Execution time Memory
506320 2022-01-12T02:03:43 Z akshtsinghania Collecting Mushrooms (NOI18_collectmushrooms) C++14
19 / 100
 22 ms 16980 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long




void solve(){
	int r,c,d,k;
	cin>>r>>c>>d>>k;
	vector<vector<char>> g(r+1,vector<char>(c+2));
	vector<vector<int>> prefix(r+2,vector<int>(c+2));

	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>g[i][j];
			if(g[i][j]=='S'){
				int one=1;
				int start_x=max(one,i-d),start_y=max(one,j-d);
				int end_x=min(r+1,i+d),end_y=min(c+1,j+d);
				//cout<<start_x<<" "<<start_y<<" "<<end_x<<" "<<end_y<<endl;
				prefix[start_x][start_y]++;
				prefix[end_x][end_y]++;
				prefix[start_x][end_y]--;
				prefix[end_x][start_y]--;
			}
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			prefix[i][j]=prefix[i][j]
					+prefix[i-1][j]
					+prefix[i][j-1]
					-prefix[i-1][j-1];	
		}
	}
	int ans=0;
	for(int i=0;i<=r;i++){
		for(int j=0;j<=c;j++){
			if(prefix[i][j]>=k&&g[i][j]=='M')
			{
				ans++;
			}
			//cout<<prefix[i][j]<<"\t";
		}
		//cout<<endl;
	}
	cout<<ans<<endl;

}

signed main(){
	cin.tie(NULL);
	cout.tie(NULL);
	//setIO("paintbarn");
	ios_base::sync_with_stdio(NULL);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;	
}
/*
4 4 4 1 
.... 
.M.. 
..MM 
...S
_____

5 5 1 1
....M 
.M... 
..S.. 
.S... 
...M.
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16980 KB Output is correct
2 Incorrect 16 ms 16980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

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