Submission #425454

#	Time	Username	Problem	Language	Result	Execution time	Memory
425454		errorgorn	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	25 ms	22028 KiB

mushrooms

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
int n,m,k,r,i,j,l,d;
vector<int> v[500005];
vector<ii> memo;
char c;
int sum(int i1,int i2, int j1,int j2){
	return (v[i2][j2]-v[i1][j2]-v[i2][j1]+v[i1][j1]);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&k);
	for(int x=0;x<=n;x++){
		v[x].push_back(0);
	}
	for (int x=0;x<m;x++){
		v[0].push_back(0);
	}
	for (int x=1;x<=n;x++){
		getchar();
		for (int y=1;y<=m;y++){
			c=getchar();
			i=v[x-1][y]+v[x][y-1]-v[x-1][y-1];
			if (c=='S') i++;
			else if(c=='M') memo.push_back(ii (x,y));
			v[x].push_back(i);
		}
	}
	/*for (int x=0;x<=n;x++){
		for (int y=0;y<=m;y++){
			printf("%d ",v[x][y]);
		}
		printf("\n");
	}*/
	l=memo.size();
	for (int x=0;x<l;x++){
		i=memo[x].first,j=memo[x].second;
		if (sum(max(0,i-r-1),min(n,i+r),max(0,j-r-1),min(m,j+r))>=k) d++;
	}
	printf("%d\n",d);
}

Compilation message (stderr)

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

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