Submission #170349

#	Time	Username	Problem	Language	Result	Execution time	Memory
170349		ngmh	Collecting Mushrooms (NOI18_collectmushrooms)	C++11	100 / 100	82 ms	28516 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

int r, c, d, k, h, nx1, nx2, ny1, ny2;
char t;
vector<pair<int, int> > mushrooms;
int main(){
	cin >> r >> c >> d >> k;
	int grid[r+5][c+5], sums[r+5][c+5];
	memset(grid, 0, sizeof(grid));
	memset(sums, 0, sizeof(sums));
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= c; j++){
			cin >> t;	
			if(t == 'S') grid[i][j] = 1;
			else if(t == 'M') mushrooms.push_back(make_pair(i, j));
		}
	}
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= c; j++){
			 sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + grid[i][j];
		}
	}
	for(int i = 0; i < mushrooms.size(); i++){
		nx1 = max(1, mushrooms[i].first-d);
		nx2 = min(r, mushrooms[i].first+d);
		ny1 = max(1, mushrooms[i].second-d);
		ny2 = min(c, mushrooms[i].second+d);
		if((sums[nx2][ny2] - sums[nx1-1][ny2] - sums[nx2][ny1-1] + sums[nx1-1][ny1-1]) >= k) h++;
	}
	cout << h;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mushrooms.size(); i++){
                 ~~^~~~~~~~~~~~~~~~~~

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