Submission #533870

#	Time	Username	Problem	Language	Result	Execution time	Memory
533870		gilbirb	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	60 / 100	2077 ms	6496 KiB

mushrooms

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
typedef long long ll;
using namespace std;

ll r, c, d, k, ans;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
ll grid[10000][10000];

bool inside(ll x, ll y){
	return (x >= 1 && y >= 1 && x <= r && y <= c);
}

void check(ll x, ll y){
	ll x1, x2, y1, y2;
	x1 = x-d; x2 = x+d; y1 = y-d; y2 = y+d;
//	cout << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
	for(int i = x1; i <= x2; i++){
		for(int j = y1; j <= y2; j++){
			if(!inside(i,j)) continue;
			if(grid[i][j] != -1){
				grid[i][j]++;
				if(grid[i][j] == k){
					ans++;
				}
			}
		}
	}
}

int main(){
	cin >> r >> c >> d >> k;
	vector<pair<ll,ll>>spr;
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= c; j++){
			char f; cin >> f;
			if(f == '.') grid[i][j] = -1;
			else if(f == 'M') grid[i][j] = 0;
			else{
				spr.pb({i,j});
				grid[i][j] = -1;
			}
		}
	}
	for(pair<ll,ll> x : spr){
		check(x.fi, x.se);
	}
	cout << ans << "\n";
}

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