Submission #146965

#	Time	Username	Problem	Language	Result	Execution time	Memory
146965		gs14004	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	34 ms	20368 KiB

mushrooms

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 500005;

int n, m, d, k;
string s[MAXN];
char buf[MAXN];
vector<vector<int>> dx;

void add(int sx, int ex, int sy, int ey){
	sx = max(sx, 0); ex = min(ex, n - 1);
	sy = max(sy, 0); ey = min(ey, m - 1);
	if(sx <= ex && sy <= ey){
		dx[sx][sy]++;
		if(ey + 1 < m) dx[sx][ey+1]--;
		if(ex + 1 < n) dx[ex+1][sy]--;
		if(ex + 1 < n && ey + 1 < m) dx[ex+1][ey+1]++;
	}
}

int main(){
	scanf("%d %d %d %d",&n,&m,&d,&k);
	dx.resize(n);
	for(int i=0; i<n; i++){
		scanf("%s", buf);
		s[i] = buf;
		dx[i].resize(m);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(s[i][j] == 'S'){
				add(i - d, i + d, j - d, j + d);
			}
		}
	}
	int ret = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(i) dx[i][j] += dx[i-1][j];
			if(j) dx[i][j] += dx[i][j-1];
			if(i&&j) dx[i][j] -= dx[i-1][j-1];
			if(s[i][j] == 'M' && dx[i][j] >= k) ret++;
		}
	}
	cout << ret << endl;
}

Compilation message (stderr)

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

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