Submission #330182

#	Time	Username	Problem	Language	Result	Execution time	Memory
330182		oak	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	0 / 100	2231 ms	219756 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
int fw[500002];
void upd(int po,int val){
	for(;po<=500000;po+=(po&-po)){
		fw[po]+=val;
	}
}
int qry(int po){
	int ret = 0;
	for(;po>0;po-=(po&-po)){
		ret += fw[po];
	}
	return ret;
}
int main(){
	int n,m,i,j,d,k;
	scanf("%d %d %d %d",&n,&m,&d,&k);
	char inp[m+1];
	int sum[n+2][m+2];
	memset(sum,0,sizeof sum);
	vector<int> mr[n+1];
	for(i=1;i<=n;i++){
		scanf("%s",inp+1);
		for(j=1;j<=m;j++){
			if(inp[j] == 'S'){
				sum[max(1,i-d)][max(1,j-d)] += 1;
				sum[max(1,i-d)][min(m,j+d)+1] -= 1;
				sum[min(n,i+d)+1][max(1,j+d)] -= 1;
				sum[min(n,i+d)+1][min(m,j+d)+1] += 1;
			}else if(inp[j] == 'M'){
				mr[i].push_back(j);
			}
		}
	}
	int ans = 0;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(sum[i][j]){
				//printf("Upd (%d,%d) : %d\n",i,j,sum[i][j]);
				upd(j,sum[i][j]);
			}
		}
		for(auto x: mr[i]){
			int test = qry(x);
			//printf("test (%d,%d) : %d\n",i,x,test);
			if(test >= k)ans++;
		}
	}
	printf("%d",ans);
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  scanf("%d %d %d %d",&n,&m,&d,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%s",inp+1);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21