Submission #925627

#	Time	Username	Problem	Language	Result	Execution time	Memory
925627		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	17 ms	24804 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;

const ll mod=1e9+7;
const ll inf=mod;
const int N=5e5+4;

int n,m,d,r;

void solve(){
	cin>>n>>m>>d>>r;
	string c[n+10];
	int la[n+5][m+5],used[n+5][m+5];
	for(int i=0; i<=n+2; ++i) for(int j=0; j<=m+2; ++j) { la[i][j]=0;used[i][j]=0;}
	for(int i=1; i<=n; ++i) {
		cin>>c[i];
		for(int j=1; j<=m; ++j) {
			if(c[i][j-1]!='S') continue;
		//	cout<<i<<' '<<j<<endl;
			la[max(i-d,1)][max(j-d,1)]+=1;
			la[max(i-d,1)][min(j+d,m+2)+1]-=1;
			la[min(i+d,n+2)+1][max(j-d,1)]--;
			la[min(i+d,n+2)+1][min(j+d,m+2)+1]++;
		}
	}
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j){
			used[i][j]=used[i][j-1]+la[i][j];
			//cout<<used[i][j]<<' ';
			//if(j==m)cout<<endl;
		}
		for(int j=1; j<=m; ++j) used[i][j]+=used[i-1][j];
	}
	int z=0;
	int mx=0;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
		if(c[i][j-1]=='M' && used[i][j]>=r) ++mx;
	}
	cout<<mx<<endl;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1;
	//	cin>>tt;
	while(tt--) {
		solve();
	}
}

Compilation message (stderr)

mushrooms.cpp: In function 'void solve()':
mushrooms.cpp:41:6: warning: unused variable 'z' [-Wunused-variable]
   41 |  int z=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